Question

Eșuînd în a-și regăsi adevărata identitate, Brush se refugiază în magicul tărâm al arborilor. Arbotra o sună și îi dă următoarea problemă: se dă un arbore cu N noduri, o rădăcină fixată, și M întrebări de forma: câte perechi neordonate de noduri pot forma, luând noduri doar din subarborele nodului X (inclusiv pe X).

Cerința
Ajutați-o pe Brush să răspundă cât mai repede la intrebările lui Arbotra.

Date de intrare
Fișierul de intrare arbrush.in va conține pe prima linie 3 numere naturale, numărul N, M și Root, separate de un spațiu. Următoarele N-1 linii vor conține două numere naturale a și b (între 1 și N), separate de un spațiu, cu semnificația că există muchie între nodurile a și b. Ultima linie a fișierului de intrare (linia N+1) va conține M numere separate de căte un spațiu, acestea vor semnifica cele M întrebari cerute de Arbotra.

Date de ieșire
Fișierul de ieșire arbrush.out va conține M linii, aflându-se răspunsul la fiecare întrebare cerută (în ordinea cerută în fișierul de intrare).

Restricții și precizări
2 ≤ N, M ≤ 27040
1 ≤ Root ≤ N
Uituc de fel, Arbotra poate pune aceeași întrebare de mai multe ori.



Exemplu
arbrush.in

8 4 1
1 2
2 3
2 5
5 6
6 7
6 8
1 4
6 4 5 2
arbrush.out

3
0
6
15
Explicație
Pentru prima întrebare, răspunsul este 3, deoarece în subarborele nodului 6 există 3 noduri: 6, 7, 8, cu care pot forma perechile {6, 7}, {7, 8}, {6, 8}

Pentru a doua întrebare răspunsul este 0, deoarece subarborele lui 4 are doar un nod, pe el înșusi și nu se pot forma perechi de câte două noduri.

Pentru a treia întrebare răspunsul este 6, deoarece în subarborele nodului 5 există 4 noduri: 5, 6, 7, 8, perechile formate sunt {6, 8}, {5, 6}, {7, 8}, {5, 8}, {5, 7}, {6, 7}

Pentru a patra întrebare răspunsul este 15.

INDICATII DE REZOLVARE
Indicații de rezolvare


Varianta 1: Complexitate: O(N*M) – se obtin doar 40 de puncte

Putem face câte o parcurgere DF la fiecare query, astfel numărăm toate nodurile din subarborele lui X, având grijă să nu mergem spre rădăcină. Fie S numărul de noduri din subarborele lui X, răspunsul este C2SCS2

Varianta 2: Complexitate: O(N+M) – se obtin 100 puncte

Ținem o dinamică D[x] = câte noduri există în subarborele lui x, calculăm vectorul D cu o parcurgere DF, actualizând costurile la întoarcere. Recurența

D[x] = D[fiu1] + D[fiu2] + … D[fiuK] + 1, unde K este numărul de fii a lui x.

Răspunsul la fiecare întrebare este C2D[x]CD[x]2. Pentru fiecare răspuns la întrebare complexitatea este O(1).

Pe mine ma intereseaza varianta 2.

Answer 1

Fisierul respectiv face o parcurgere a arborelui prin referinte descendente, de tip tata. Mai intai spune parintele si apoi copilul.
Programarea dinamica de obicei se formeaza de la coada la capat. Incepi cu cea mai simpla unitate si ajungi dupa aceea la cea mai complexa.
Asta inseamna ca arborele ar trebui parcurs prin referinte ascendente, de la nodurile terminale pana la radacina.
Transformarea din referinte descendente in referinte ascendente ia destul de multe operatii, pentru ca trebuie sa iei terminalele de la cel cu cea mai mica eticheta la cel cu cea mai mare, altfel risti sa faci cicluri in citire(citesti parinte, apoi fiu, apoi acelasi tata, apoi iar fiul initial)

In arborele tau de aici, incepi cu 3, apoi cu 4, 7,8 si apoi il iei pe 6, care devine nod terminal dupa inlaturarea lui 7 si 8.
La final o sa ai doi vectori t si pt(parinte terminal) care o sa arate asa
t:3 4 7 8 6 5 2 
pt:2 1 6 6 4 2 1

Odata aflati acesti 2 vectori faci urmatorii pasi per cautare
1) Setezi un vector de cost cu 1(fiecare nod se cunoaste pe el insusi)
2) verifici pentru un nod parinte daca este un succesor al nodului X la care cauti(altfel nu are sens sa faci calcule partiale)
3) incepi sa faci calcule partiale

Fisierul CPP are o gramada de alte functii de le-am mai facut eu comentate pentru diverse teste. Dar oricum, ma tem ca acea transformare din referinte descendente in referinte ascendente o sa faca programul incet.
Oricum, si dimensiunile vectorilor sunt mici, doar de 20, este ceva demonstrativ cam cum s-ar face pornind de la terminale. 

eef68eeb8fd6f5580449f875cfe9b8c7.cpp