---
# System prepended metadata

title: AISD 3

---

# 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
    
