# AISD 3

## Zadanie 3
1. znajdujemy centroid (*) (w przypadku gdy istnieją dwa możemy wybrać dowolny - asymptotycznie nie ma to wpływu na złożoność algorytmu)
2. Ukorzeniamy drzewo w centroidzie
3. W poddrzewach znajdujemy odległości wszystkich wierzchołków od centroidu określonego powyżej
- dla każdego poddrzewa z osobna sortujemy odległości i zwracamy
I) znajdujemy listę odległości
II) ilość par wierzchołków takich że suma ich odległości do korzenia jest równa C (to sa zle przypadki - "dwa pointery")
4. Łączymy listy (z zachowaniem porządku - po prostu sortujemy po zwykłym merge'u)
5. "dwa pointery"

(*) znajdowanie centroidów
-> preprocessing - wyznaczenie rozmiaru poddrzewa dla każdego wierzchołka (DFS O(N))
wchodzimy do korzenia:
-> sprawdzamy czy korzeń nie jest centroidem
-> jeśli tak -> zwracamy go
-> jeśli nie -> wchodzimy do "największego" syna - zwracamy jego wynik

( ** ) sprawdzenie czy wierzchołek jest centroidem
-> dla każdego dziecka:
-> jeśli jego rozmiar jest większy niż $\lceil{n/2}\rceil$ -> nie jest
-> jeśli (n-1) - suma dzieci jest większa niż $\lceil{n/2}\rceil$ -> nie jest
-> wpp jest