petarbore

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, valorea de pe o muchie reprezentand cate minute dureaza ca un semnal sa parcurga acea muchie. 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.

Berlintul are forma unui arbore cu $N$ noduri (graf conex aciclic), fiecare nod reprezentand o intersectie, valoarea de pe o muchie reprezentand cate minute dureaza sa fie parcursa acea muchie. 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.

Teroristii opereaza astfel: acestia se ascund in mai multe intersectii, nu neaparat vecine. 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.

Teroristii opereaza astfel: acestia se ascund in mai multe intersectii, nu neaparat vecine. Fiecare terorist dintr-o intersectie va trimite un semnal posibililor teroristi din intersectiile vecine (legate printr-o muchie care porneste din intersectia curenta). 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.

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 <tex> \frac{S}{2^n} </tex>. 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. Mai mult, va cere aceasta valoare *modulo 998244353*.

$E$ este de forma <tex> \frac{S}{2^n} </tex>. 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. Mai mult, va cere aceasta valoare *modulo 998244353*. Altfel spus, $S$ este suma timpilor minimi in care explodeaza o bomba, pentru toate combinatiile de intersectii.

h2. Date de intrare

h2. Date de ieşire

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

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

h2. Restricţii

*Durata muchiilor va fix maxim $10^9^$.*
 

table(restrictii). |_. Subtask |_. Punctaj |_. Restricţii |

* | $1$ | $25 puncte$ | $1 ≤ $N$ ≤ 15$ |
* | $2$ | $25 puncte$ | $1 ≤ $N$ ≤ 200$ |
* | $3$ | $25 puncte$ | $1 ≤ $N$ ≤ 5000$ si muchiile vor avea costul *$1 sau 2$* |
* | $4$ | $25 puncte$ | $1 ≤ $N$ ≤ 5000$ |

* | $1$ | $20 puncte$ | $1 ≤ $N$ ≤ 15$ |
* | $2$ | $20 puncte$ | $1 ≤ $N$ ≤ 200$ |
* | $3$ | $20 puncte$ | $1 ≤ $N$ ≤ 5000$ si muchiile vor avea durate de *$1 sau 2$* |
* | $4$ | $20 puncte$ | $1 ≤ $N$ ≤ 5000$ si muchiile vor avea durate diferite |
* | $5$ | $20 puncte$ | $1 ≤ $N$ ≤ 5000$ |

h2. Exemplu

h3. Explicaţie

Pentru usurinta, vom nota $f(X)$ ca fiind timpul dupa care explodeaza o bomba daca teroristii se ascund in nodurile din submultimea $X$. Avem, astfel:
 

$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$.