== include(page="template/taskheader" task_id="petarbore") ==
Ministrul Brantz urmeaza sa soseasca maine la Berlint, pentru a negocia cu reprezentativii Westalisului. Dar teroristii westalieni au alte planuri in cap: sa porneasca un razboi.
Berlintul are forma unui arbore cu $N$ noduri, fiecare nod reprezentand o intersectie, muchiile reprezentand cate minute dureaza ca un semnal sa ajunga dintr-o intersectie intr-alta. Teroristii se pot ascunde in orice intersectie. Agentul Twilight incearca sa ii impiedice din a starni un razboi intre Westania si Ostania si vrea sa afle cat timp are la dispozitie pentru a-i opri.
Se da un arbore cu *N* noduri, fiecare muchie avand un cost. Pentru o submultime *X* de noduri ale arborelui definim urmatoarea functie:
Teroristii opereaza astfel: fiecare terorist dintr-o intersectie va trimite un semnal posibilor teroristi din intersectiile vecine. Daca exista un terorist care primeste un semnal, aceasta va detona o bomba. Twilight vrea sa opreasca orice detonare de bomba, asa ca, in caz ca mai multi teroristi vor primi semnale, el este interesat de primul terorist care il primeste.
$f(X) = costul minim al unei muchii a carei capete fac parte din multimea *X*$
Twilight va analiza toate combinatiile de intersectii in care teroristii se pot ascunde, si va determina pentru fiecare timpul minim in care un terorist primeste semnal de la un vecin. In final, el vrea sa calculeze expected-ul de cat timp trece pana explodeaza o bomba. Deoarece matematica este unul dintre multele skill-uri pe care le are, Twilight a dedus ca acest expected
$E$ este de forma $S / 2^n^$. El se descurca sa calculeze $2^n^$, dar nu dispune de mult timp pentru a calcula $S$, asa ca va roaga pe voi sa il aflati.
Sa se calculeze *suma valorilor lui f(X)*, pentru toate submultimile *X*, *modulo 998244353*.
h2. Date de intrare
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 timpul necesar pentru ca un semnal din $x$ sa ajunga in $y$ si invers.
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
