FMI NO STRESS 12 | Red Splay BTreap

Se definește un Red Black Tree ca fiind un arbore binar cu următoarele proprietăți:

• fiecare nod este colorat fie în negru, fie în roșu;
• fiecare nod are fie $2$ fii, fie $0$ fii (este frunză);
• fiecare frunză este colorată în negru;
• rădăcina este colorată în negru;
• 2 noduri conectate printr-o muchie nu pot fi amândouă roșii;
• $\forall u$, nod în arbore, atunci, $\forall v, w$, frunze din subarborele lui $u$, numărul de noduri colorate în negru de pe lanțul de la $u$ la $v$ este egal cu numărul de noduri colorate în negru de pe lanțul de la $u$ la $w$.

Se definește un Red Splay BTreap ca fiind un arbore binar cu următoarele proprietăți:

• fiecare nod este colorat fie în negru, fie în roșu;
• fiecare nod are fie 2 fii, fie 0 fii (este frunză);
• fiecare frunză este colorată în negru;
• rădăcina este colorată în negru;
• 2 noduri conectate printr-o muchie nu pot fi amândouă roșii;
• $\forall u$, nod în arbore, atunci, $\forall v, w$, frunze din subarborele lui $u$, diferența în modul dintre numărul de noduri colorate în negru de pe lanțul de la $u$ la $v$ și numărul de noduri colorate în negru de pe lanțul de la $u$ la $w$ este cel mult 1.

Cerință

Se dă un arbore cu $N$ noduri numerotate de la $1$ la $N$ (care se știe că admite o colorare de Red Black Tree). Aflați câte dintre colorările sale (cu roșu și negru) formează un Red Splay BTreap, dar nu un Red Black Tree, modulo $998 \ 244 \ 353$.

Date de intrare

Prima linie va conține $N$, numărul de noduri din arbore. Pe următoarele $N-1$ linii se află muchiile grafului, fiecare conține câte o pereche de noduri $(u, v)$, semnificând că în arbore există muchie între nodurile $u$ și $v$.

Date de ieșire

Se va afișa un singur număr, reprezentând numărul de moduri de a colora arborele astfel încât să formeze un Red Splay BTreap, dar nu Red Black Tree, modulo $998 \ 244 \ 353$.

Restricții și precizări

• $1 \leq N \leq 99 \ 615$;
• $1 \leq u, v \leq N$;
• Arborele are rădăcina în nodul $1$;
• Pentru teste valorând $15$ puncte, $1 \leq N \leq 11$;
• Pentru teste valorând alte $16$ puncte, $1 \leq N \leq 31$;
• Pentru restul de $69$ de puncte, nu există restricții suplimentare.

Exemplul 1

stdin

5
1 3
3 2
1 4
3 5

stdout

1

Explicație

Singurul mod de a colora nodurile este BBBBB.

Exemplul 2

stdin

13
1 3
3 2
2 8
3 5
5 4
5 7
7 6
1 10
10 9
10 11
2 12
7 13

stdout

6

Explicație

Cele $6$ moduri de a colora arborele sunt: BBRBBBBBBBBBB, BBBBRBBBBBBBB, BRBBRBBBBBBBB, BBBBBBRBBBBBB, BRBBBBRBBBBBB, BBRBBBRBBRBBB.

Exemplul 3

stdin

15
1 2
2 5
2 3
3 4
1 9
9 7
7 6
7 8
9 11
11 10
11 13
13 12
3 14
13 15

stdout

12

Explicație

Cele $12$ moduri de a colora arborele sunt: BBBBBBBBRBBBBBB, BBRBBBBBRBBBBBB, BBBBBBBBBBRBBBB, BBRBBBBBBBRBBBB, BBBBBBRBBBRBBBB, BBRBBBRBBBRBBBB, BBBBBBBBBBBBRBB, BBRBBBBBBBBBRBB, BBBBBBRBBBBBRBB, BBRBBBRBBBBBRBB, BBBBBBBBRBBBRBB, BRBBBBBBRBBBRBB.