FMI NO STRESS 12 | Red Splay BTreap

This was the problem page during the contest. Access the current page here.
Time limit: 1.5s Memory limit: 1024MB Input: Output:

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 22 fii, fie 00 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;
  • u\forall u, nod în arbore, atunci, v,w\forall v, w, frunze din subarborele lui uu, numărul de noduri colorate în negru de pe lanțul de la uu la vv este egal cu numărul de noduri colorate în negru de pe lanțul de la uu la ww.

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;
  • u\forall u, nod în arbore, atunci, v,w\forall v, w, frunze din subarborele lui uu, diferența în modul dintre numărul de noduri colorate în negru de pe lanțul de la uu la vv și numărul de noduri colorate în negru de pe lanțul de la uu la ww este cel mult 1.

Cerință

Se dă un arbore cu NN noduri numerotate de la 11 la NN (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 353998 \ 244 \ 353.

Date de intrare

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

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 353998 \ 244 \ 353.

Restricții și precizări

  • 1N99 6151 \leq N \leq 99 \ 615;
  • 1u,vN1 \leq u, v \leq N;
  • Arborele are rădăcina în nodul 11;
  • Pentru teste valorând 1515 puncte, 1N111 \leq N \leq 11;
  • Pentru teste valorând alte 1616 puncte, 1N311 \leq N \leq 31;
  • Pentru restul de 6969 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 66 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 1212 moduri de a colora arborele sunt: BBBBBBBBRBBBBBB, BBRBBBBBRBBBBBB, BBBBBBBBBBRBBBB, BBRBBBBBBBRBBBB, BBBBBBRBBBRBBBB, BBRBBBRBBBRBBBB, BBBBBBBBBBBBRBB, BBRBBBBBBBBBRBB, BBBBBBRBBBBBRBB, BBRBBBRBBBBBRBB, BBBBBBBBRBBBRBB, BRBBBBBBRBBBRBB.

Log in or sign up to be able to send submissions!