Na XXX Olimpiadzie Informatycznej zawodnicy mierzyli się z zadaniem “Zboże”. Pełną treść zadania można znaleźć na oficjalnej stronie Olimpiady. W dużym skrócie w zadaniu było dane ukorzenione drzewo z wagami na krawędziach oraz ciąg wierzchołków z tego drzewa. Dla każdego wierzchołka z ciągu należało policzyć jego sumaryczną odległość do wszystkich wierzchołków leżących w ciągu przed nim.
Rozwiązanie I
Wykonamy programowanie dynamiczne na drzewie. Po kolei będziemy przeglądać wierzchołki z ciągu. W każdej chwili każdy z wierzchołków na drzewie będzie pamiętał:
- n[v] – Ile jest wierzchołków z ciągu w jego poddrzewie
- S[v] – Jaka jest sumaryczna odległość od wierzchołków z ciągu w danym poddrzewie do tego wierzchołka
Gdy dodajemy nowy wierzchołek, przechodzimy w górę drzewa i liczymy sumaryczną długość do pozostałych wierzchołków. W tym celu utworzymy dwie zmienne: suma oraz sciezka. W zmiennej suma będziemy przechowywać sumaryczną odległość do wszystkich pozostałych wierzchołków (które były wcześniej w ciągu), a w zmiennej sciezka będziemy pamiętać długość ścieżki z tego wierzchołka do jego przodka.
Zaczynamy od wierzchołka w którym jesteśmy. Wiemy, że wszystkie ścieżki do wierzchołków w tym poddrzewie sumują się do S[v]. Inicjujemy zatem zmienną suma na S[v] a zmienna sciezka na 0.
Powtarzamy dopóki nie dojdziemy do korzenia. Idziemy do naszego ojca p. Powiedzmy, że krawędź między nami a naszym ojcem ma wagę w. Do zmiennej sciezka dodajemy wartość w. Od S[p] odejmujemy S[v] + w * n[v] aby uzyskać jaka jest sumaryczna odległość od wierzchołków spoza poddrzewa z którego właśnie przyszliśmy. Następnie do tej wartości dodajemy sciezke przemnożoną przez n[p] – n[v]. Wynik naszych obliczeń dodajemy do zmiennej suma. Za v podstawiamy p.
Po dojściu do korzenia w zmiennej suma mamy interesującą nas wartość. Musimy jeszcze uaktualnić wszystkie wartości na ścieżce między wierzchołkiem a korzeniem i możemy przejść do kolejnego wierzchołka w ciągu.
Złożoność naszego algorytmu to długość ciągu wierzchołków (w najgorszym przypadku n) razy wysokość drzewa (w najgorszym przypadku n). Zatem O(n2). Zwróćmy jednak uwagę, że jeśli wysokość drzewa jest logarytmiczna, to złożoność naszego algorytmu wyniesie O(n lg n).
Rozwiązanie II
Wyobraźmy sobie, że wszystkie wierzchołki w drzewie leżą na jednej ścieżce (załóżmy ponadto, że wierzchołki numerowane są w takiej kolejności, że wierzchołek o numerze i jest ojcem wierzchołka o numerze i+1). Choć nasz poprzedni algorytm dla tego typu drzewa działa w czasie O(n2), to istnieje prosty algorytm liczący rozwiązanie w czasie O(n lg n).
Dla każdego wierzchołka liczymy podobne wartości jak poprzednio:
- n[v] – ile jest wierzchołków z ciągu w tym wierzchołku (lub prościej: 1 jeśli wierzchołek wystąpił już w ciągu i 0 jeśli nie)
- S[v] – sumaryczna długość z ścieżek z tego wierzchołka do korzenia (lub prościej: długość ścieżki z tego wierzchołka do korzenia jeśli wierzchołek wystąpił już w ciągu i 0 jeśli nie)
Ponadto wcześniej liczymy w czasie liniowym odległość od korzenia do każdego innego wierzchołka. Oznaczmy te odległości jako odl[v].
Aby policzyć sumaryczną odległość z wierzchołka v do wszystkich pozostałych wierzchołków (które były już w ciągu) dzielimy je na dwie części. Te które są bliżej korzenia i te które są dalej od korzenia.
Zacznijmy od tych które są bliżej korzenia. Niech S będzie sumą odległości do korzenia wierzchołków, które są bliżej korzenia niż v. Mówiąc prościej S := S[1] + S[2] + ... + S[v-1]. Tak samo liczymy ile tych wierzchołków jest tn := n[1] + n[2] + ... + n[v-1]. Sumaryczna odległość wierzchołka v do tych wierzchołków jest równa tn * odl[v] - S.
Podobnie sprawa wygląda z wierzchołkami, które są dalej od korzenia. Jeśli S := S[v] + ... + S[n] oraz tn := n[v] + ... n[n] to sumaryczna odległość od wierzchołka v do tych wierzchołków wynosi S - tn * odl[v].
Na końcu musimy uaktualnić wartości n[v] := 1 oraz S[v] := odl[v].
Potrzebujemy strukturę danych, która jest w stanie uaktualniać szybko wartości n[v] oraz S[v] oraz jest w stanie obliczać szybko sumy S[1] + ... + S[v-1] oraz S[v+1] + ... + S[n]. Drzewo przedziałowe typu punkt – przedział umożliwia wykonanie obu operacji w czasie O(lg n). Dzięki tej strukturze danych możemy rozwiązać ten przypadek zadania w czasie O(n lg n).
Rozwiązanie III
Drzewa mogą być różne. Mogą być zbalansowane i mieć wysokość logarytmiczną albo być wręcz jedną długą ścieżką i mieć wysokość liniową. Rzecz w tym, że w obu tych sytuacjach, wiemy jak policzyć rozwiązanie w czasie liniowo-logarytmicznym. Czas połączyć te dwa algorytmy ze sobą i stworzyć algorytm, który będzie działał dla dowolnego drzewa. W tym celu użyjemy techniki zwanej heavy – light decomposition.
Niech dany będzie wierzchołek v oraz poddrzewo zaczenione w tym wierzchołku. Powiedzmy, że w tym poddrzewie jest n wierzchołków. Jeśli u jest synem v i w poddrzewie u jest co najmniej n/2 wierzchołków, to krawędź (v, u) nazywamy ciężką krawędzią. W przeciwnym przypadku jest ona lekką krawędzią. Zauważmy, że wierzchołek v może być połączony ciężką krawędzią jedynie z co najwyżej jednym swoim synem. Ścieżkę złożoną jedynie z ciężkich krawędzi nazywamy ciężką ścieżką.
Ponieważ żaden wierzchołek nie może być połączony krawędzią ciężką z dwoma swoimi synami, to ścieżki ciężkie w drzewie są rozłączne.
Twierdzenie. W dowolnym drzewie, każda ścieżka z korzenia do dowolnego wierzchołka (twierdzenie można uogólnić na dowolne ścieżki) składa się z logarytmicznej liczby krawędzi lekkich oraz z logarytmicznej liczby ciężkich ścieżek.
Dowód. Schodząc z korzenia w dół. Za każdym razem gdy przechodzimy lekką krawędzią to liczba wierzchołków w danym poddrzewie zmniejsza się dwukrotnie. Zatem możemy przejść jedynie po logarytmicznej liczbie krawędzi lekkich. Ponadto jeśli przechodząc po krawędziach ciężkich nie przeszliśmy w międzyczasie po krawędzi lekkiej, to te krawędzie ciężkie tworzą ciężką ścieżkę. Zatem i ich nie może być więcej niż logarytmicznie wiele.
Nasza idea jest teraz prosta (ale dość trudna przy implementacji). Idąc teraz z pewnego wierzchołka do korzenia, będziemy natrafiać na lekkie krawędzie i ciężkie ścieżki. Idąc po lekkiej krawędzi wykonujemy algorytm z rozwiązania pierwszego. Idąc po ciężkiej ścieżce, uruchamiamy algorytm z rozwiązania drugiego. Ponieważ mamy jedynie logarytmicznie wiele ścieżek ciężkich i lekkich krawędzi oraz algorytm dla lekkich krawędzi działa w najgorszym czasie w czasie stałym, a algorytm dla ścieżek działa w czasie logarytmicznym, to całe nasze rozwiązanie działa w czasie O(n lg2 n).
