== include(page="template/taskheader" task_id="petarbore") ==

Poveste şi cerinţă...

Se da un arbore cu *N* noduri, fiecare muchie avand un cost. Pentru o submultime *X* de noduri ale arborelui definim urmatoarea functie:
 
$f(X) = costul minim al unei muchii a carei capete fac parte din multimea *X*$
 
Sa se calculeze *suma valorilor lui f(X)*, pentru toate submultimile *X*, *modulo 998244353*.

h2. Date de intrare

Fişierul de intrare $petarbore.in$ ...

Fişierul de intrare $petarbore.in$ va contine pe prima linie $N$, reprezentand numarul de noduri ale arobrelui.
Pe urmatoarele $N-1$ linii se vor afla muchiile arborelui, sub forma $x y z$ reprezentand muchia si costul sau, in aceasta ordine.

h2. Date de ieşire

În fişierul de ieşire $petarbore.out$ ...

În fişierul de ieşire $petarbore.out$ va contine un singur numar, reprezentand suma *modulo 998244353*.

h2. Restricţii

* $... ≤ ... ≤ ...$

* Pentru $10 puncte$, $1 ≤ $N$ ≤ 15$.
* Pentru $20 puncte$, $1 ≤ $N$ ≤ 200$.
* Pentru $20 puncte$, $1 ≤ $N$ ≤ 5000$ si muchiile vor avea costul *$1 sau 2$*.
* Pentru $50 puncte$, $1 ≤ $N$ ≤ 5000$.

h2. Exemplu
table(example). |_. petarbore.in |_. petarbore.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

| 4
1 2 1
1 3 1
3 4 2
| 10
|

h3. Explicaţie

...

$f({1, 2}) = 1, f({1, 3}) = 1, f({1, 2, 3}) = 1, f({3, 4}) = 2, f({1, 2, 4}) = 1, f({1, 3, 4}) = 1, f({2, 3, 4}) = 2, f({1, 2, 3, 4}) = 1$
Restul submultimilor $X$, in afara de cele enumerate mai sus, au $f(X) = 0$
Suma valorilor lui $f(X)$ va fi:
$1 + 1 + 1 + 2 + 1 + 1 + 2 + 1 = 10$

== include(page="template/taskfooter" task_id="petarbore") ==