De ce contează?
Vrei să afli, pentru fiecare nod al unui arbore, un răspuns „dacă nodul ăsta ar fi rădăcina” — de exemplu suma distanțelor de la el la toate celelalte. Soluția leneșă: fixezi pe rând fiecare nod ca rădăcină și refaci tot DP-ul. E ca și cum ai recalcula toată harta de fiecare dată când te muți cu o casă mai încolo. Rerădăcinarea observă altceva: când muți rădăcina la un vecin, aproape tot răspunsul rămâne valabil — doar o mică parte trebuie ajustată.
Intuiția
DP-ul clasic pe arbore îți dă un răspuns pentru o singură rădăcină fixă: fiecare nod „strânge” informația din subarborele lui și o trimite în sus la părinte. Dar dacă vrei răspunsul cu fiecare nod ca rădăcină, ai N întrebări, nu una.
Ideea de aur: răspunsul pentru un nod v ca rădăcină se compune din două bucăți.
Una privește în jos, spre subarborele lui v (asta o știe deja DP-ul clasic).
Cealaltă privește în sus, spre tot restul arborelui — și aceasta o poți obține
din răspunsul părintelui, ajustând o contribuție. Deci nu recalculezi: muți
rădăcina pas cu pas, de la părinte la copil, reciclând efortul.
Ai deja DP pe arbore. Cel mai simplu: rulează-l de N ori, o dată cu fiecare nod ca rădăcină. Fixezi rădăcina, faci un DFS, citești răspunsul pentru acel nod.
Un DFS costă O(N). Repetat din fiecare nod: O(N) × N = O(N^2). La N de ordinul
10^5 înseamnă 10^10 operații — secunde bune, TLE garantat. Refaci de fiecare
dată exact aceleași subcalcule.
Rezultatele a doi vecini diferă foarte puțin. Fac DOUĂ parcurgeri. DFS1 fixează
o rădăcină (nodul 0) și calculează down[v] = contribuția „în jos” a subarborelui
lui v, plus size[v] = câte noduri are subarborele. DFS2 pornește de sus și
„mută” rădăcina de la părinte la copil: răspunsul complet al copilului = ce vede
copilul în jos + ce vede „în sus” prin părinte, obținut dintr-o formulă simplă pe
baza răspunsului deja calculat al părintelui.
Două DFS-uri, fiecare O(N), deci O(N) total. DFS1 umple down[] și size[] cu
rădăcina 0. DFS2 setează res[0] = down[0] și propagă în jos
res[copil] = res[parinte] + (n - 2*size[copil]), vizitând fiecare nod o dată.