Omówienie zadania Zboże (I etap XXX OI)

Formalna treść zadania

Dane mamy drzewo nieskierowane ważone o \(n\) wierzchołkach. Waga krawędzi łączącej wierzchołek \(a_i\) oraz \(b_i\) wynosi \(c_i\) dla \(1\leq i \leq n-1\). Następnie dane mamy \(k\) wydarzeń. Początkowo wszystkie wierzchołki są zablokowane. Każde wydarzenie polega na odblokowaniu wierzchołka \(v_i\). Po każdym zapytaniu należy wypisać sumę odległości między wszystkimi parami niezablokowanych wierzchołków.

Ponadto przez \(d(a, b)\) oznaczmy długość ścieżki z \(a\) do \(b\) oraz przez \(G\) oznaczmy drzewo z wejścia.

Pierwsze podzadanie – \(nk \leq 100\ 000\)

W tym podzadaniu limity pozwalają na bezpośrenie symulowanie liczenia wyniku. Niech \(d_i = \sum_{1 \leq a, b \leq i} d(v_a, v_b)\) będzie odpowiedzią na \(i\)-te zapytanie – czyli sumą dystansów między wszystkimi parami wierzhołków ze zbioru \(\{v_1, \dots, v_i\}\). Wówczas odpowiedź na \((i+1)\)-sze zapytanie to \[ d_{i+1} = \sum_{a, b \leq i+1} d(v_a, v_b) = \sum_{a, b \leq i} d(v_a, v_b) + 2\sum_{1 \leq j \leq i} d(v_{i+1}, v_j) = d_i + 2\sum_{1 \leq j \leq i} d(v_{i+1}, v_j). \] Zatem mając policzone \(d_i\) możemy w czasie liniowym policzyć sumę odległości między wszystkimi parami wierzchołków ze zbioru \(\{v_1, \dots, v_{i}\}\) a wierzchołkiem \(v_{i+1}\), aby otrzymać wartość \(d_{i+1}\). Możemy to obliczyć liniowo dla każdego zapytania, obliczając odległości od wierzchołka \(v_{i+1}\) używając algorytmu DFS. Ostateczna złożoność to \(O(nk)\).

Drugie podzadanie – graf tworzy ścieżkę, numery wierzchołków kolejno rosną od \(1\) do \(n\)

Ponieważ graf jest ścieżką, wierzchołki możemy utożsamić z punktami na prostej. Niech \(c_i\) będzie wagą krawędzi łączącą wierzchołek \(i\) z wierzchołkiem \(i+1\) (dla \(1 \leq i \leq n-1\)). Ponadto niech \(p_i = \sum_{j=1}^i c_j\) będzie ciągiem sum prefiksowych wag krawędzi na ścieżce. Spróbujmy zastosować pomysł z poprzedniego podzadania. Musimy zatem po odblokowaniu nowego wierzchołka \(v_{i+1}\) móc szybko obliczać \(\sum_{1\leq j\leq i}\ d(v_j, v_{i+1})\). Zauważmy, że na ścieżce odległość między dwoma wierzchołkami \(a, b\) wyraża się wzorem \(\sum_{j=a}^{b-1} c_j\). Rozważmy przypadki:

• \(v_{i+1} < v_j\). Wówczas korzystając z powyższych obserwacji widzimy, że \(d(v_j, v_{i+1}) = \sum_{l=v_{i+1}}^{v_j-1} c_l = p_{v_j-1}-p_{v_{i+1}}\)
• \(v_{i+1} > v_j\). Podobnie mamy, że \(d(v_j, v_{i+1}) = \sum_{l=v_{j}}^{v_{i+1}-1} c_l = p_{v_{i+1}-1} - p_{v_j}\)

Po posumowaniu powyższych wzorów względem \(1\leq j\leq i\) dostajemy, że zadanie sprowadza się do szybkiego obliczania \(\sum_{1\leq j \leq i, v_j > v_{i+1}} p_{v_j-1}\) oraz \(\sum_{1\leq j \leq i, v_j < v_{i+1}} p_{v_j}\). Operację znajdowania sumy na przedziale możemy zrealizować korzystając z drzew przedziałowych. Na drzewie będziemy przechowywać odpowiednie sumy prefiksowe wag odblokowanych wierzchołków, zgodnie z powyższymi wzorami. Wówczas operację odblokowania (oraz wstawienia nowej wartości sumy prefiksowej do drzewa), jak i operację sumy na przedziale możemy wykonać w czasie \(O(\log n)\). Potrzebna jest także operacja szybkiego obliczania, ile \(j\) spełnia \(v_j < v_{i+1}\). Tą operację również możemy obsługiwać wykorzystując drzewo przedziałowe – w momencie aktywacji wierzchołka \(v_{j}\) wstawiamy \(1\) na pozycji \(j\) w drzewie. Wówczas szukaną wartością dla \(v_{i+1}\) jest suma na prefiksie długości \(i\). Ostateczna złożoność algorytmu to \(O(n\log n + k\log n)\).

Pełne rozwiązanie – centroid decomposition

W problemach, w których mamy do czynienia z obliczaniem czegoś na wszystkich ścieżkach drzewa często przydatna okazuje się być technika rozbicia przez centroid. Tak też będzie i w tym przypadku. Przed wykonywaniem obliczeń stwórzmy drzewo centroidów. Wówczas każdy wierzchołek odpowiada pewnemu podgrafowi drzewa \(G\), którego jest on centroidem.

Niech \(c_1, \dots c_m\) będą centroidami podgrafów \(G\), które zawierają wierzchołek \(v_{i+1}\). Ponadto podgrafy te oznaczmy przez \(G_{c_1}, \dots, G_{c_m}\). Wówczas, aby policzyć sumę odległości między wierzchołkiem \(v_{i+1}\) a wierzchołkami \(v_1, \dots, v_i\) wystarczy, że policzymy taką sumę oddzielnie dla każdej ścieżki przechodzącej przez \(c_j\) w podgrafie \(G_{c_j}\) dla każdego \(1\leq j \leq m\). Ustalmy \(c_j\) oraz \(G_{c_j}\). Wtedy każda ścieżka wychodząca z \(v_{i+1}\) oraz przechodząca przez \(c_j\) będzie musiała wchodzić do poddrzewa innego dziecka wierzchołka \(c_j\) niż te, w którym znajduje się wierzchołek \(v_{i+1}\) w \(G_{c_j}\).

Zatem, aby sprytnie móc obliczać szukaną sumę odległości, dla każdego podgrafu \(G_v\) drzewa z wejścia o centroidzie \(v\) utrzymujmy dodatkowo:

• odległość każdego wierzchołka w \(G_v\) od wierzchołka \(v\)
• liczbę odblokowanych wierzchołków w poddrzewie każdego dziecka \(v\)
• sumę dystansów od \(v\) do wszystkich odblokowanych wierzchołków w poddrzewie każdego dziecka \(v\)
• sumaryczną liczbę odblokowanych wierzchołków w \(G_v\)
• sumę dystansów od \(v\) do wszystkich odblokowanych wierzchołków w \(G_v\)

Mając takie wartości jesteśmy w stanie w czasie stałym poznać szukaną sumę odległości oraz zaktualizować wartości dla konkretnego \(c_j\) – przykładowo liczbę odblokowanych wierzchołków w poddrzewie pewnego dziecka \(c_j\), w którym nie ma wierzchołka \(v_{i+1}\) możemy obliczyć odejmując od liczby wszystkich odblokowanych wierzchołków w \(G_{c_j}\) liczbę odblokowanych wierzchołków w poddrzewie \(c_j\), w którym jest wierzchołek \(v_{i+1}\). Ponieważ różnych interesujących centroidów jest \(O(\log n)\), to również odblokowanie wierzchołka \(v_{i+1}\) możemy zrealizować w złożoności \(O(\log n)\).

Ostateczna złożoność to \(O((n+k)\log n)\). Warto nadmienić, iż jest to rozwiązanie działające online, co sprawia, że jest dużo bardziej uniwersalne niż następne rozwiązania.

Alternatywne rozwiązanie – pierwiastek

Zadanie można również rozwiązać metodą pierwiastkową. Podzielmy zapytania na grupy składające się z \(S\) zapytań (ostatnia grupa być może będzie mniejsza). Wartość \(S\) ustalimy później. Wierzchołki odblokowywane wewnątrz tej grupy to niech będą \(u_1, \dots, u_S\) – nazwijmy je ciekawymi. Możemy wtedy w złożoności \(O(n)\) skompresować drzewo do rozmiaru \(O(S)\), żeby zawierało wszystkie wszystkie ciekawe wierzchołki. Oznaczmy drzewo z wejścia przez \(G\) oraz skompresowane drzewo przez \(T\).

Jak możemy to zrobić? Przechodząc algorytmem DFS drzewo \(G\) możemy najpierw policzyć dla każdego wierzchołka \(v\), w ilu różnych poddrzewach dzieci \(v\) znajdują się interesujące wierzchołki. Jeśli istnieją przynajmniej dwa takie poddrzewa, to wierzchołek \(v\) będzie należał do skompresowanego drzewa, zatem także staje się ciekawy. Takich wierzchołków będzie \(O(S)\) i są one wystarczające, by poprawnie skompresować drzewo. Możemy to zrobić drugim przejściem algorytmu DFS. Utrzymujmy na stosie ciekawe wierzchołki, które są odwiedzone, ale jeszcze nieprzetworzone w całości przez algorytm DFS. Gdy trafimy na ciekawy wierzchołek, to łączymy go z innym ciekawym wierzchołkiem na górze tego stosu oraz dodajemy go na stos. Żeby sprawnie przeliczać wagi na krawędziach nowego grafu \(T\) należy również spreprocessować sumę wag na ścieżce od korzenia do każdego wierzchołka w drzewie z wejścia. Wówczas możemy w czasie stałym obliczać sumę wag na dowolnej pionowej ścieżce w grafie \(G\), która zostanie zamieniona na pojedynczą krawędź w skompresowanym drzewie.

Następnie w tak skompresowanym drzewie \(T\) możemy brutalnie obliczyć odległości między wszystkimi parami wierzchołków w złożoności \(O(S^2)\) oraz zaktualizować wyniki dla każdego zapytania w grupie w czasie \(O(S)\), przeglądając ciekawe wierzchołki oraz uwzględniając w wyniku te, które zostały odblokowane wcześniej. Ostateczna złożoność algorytmu to \(O(\frac{k}{S}(n + S^2))\). Pozostaje kwestia dobrania \(S\). Ponieważ \(k\) nie przekracza \(n\), to dobierając \(S = \sqrt{n+k} = O(\sqrt{n})\) otrzymujemy złożoność \(O(n\sqrt{n})\).

Kolejne alternatywne rozwiązanie – HLD

Inną techniką skuteczną w walce z jednoczesnymi operacjami na wielu ścieżkach jest heavy–light decomposition. Początkowo wyznaczamy wszystkie „grube” ścieżki, zawsze przedłużając je o wierzchołki znajdujące się w największym poddrzewie.

Niech „strefa” wierzchołka \(v\) leżącego na grubej ścieżce \(S\) to będzie wierzchołek \(v\) oraz wszystkie wierzchołki zawarte w poddrzewach zaczynających się w dzieciach \(v\) za wyjątkiem dziecka \(v\) znajdującego się na grubej ścieżce \(S\). Następnie dla każdej grubej ścieżki utrzymujmy drzewo przedziałowe. Liść w takim drzewie będzie utrzymywał informację dotyczącą strefy pewnego wierzchołka z \(G\).

Aby sprawnie obliczać odpowiedź, w każdym przedziale bazowym odpowiadającym pionowej ścieżce od \(A\) do \(B\) drzewa \(G\) będziemy utrzymywać następujące wartości:

• liczbę odblokowanych wierzchołków na ścieżce od \(A\) do \(B\),
• sumę odległości od \(A\) do wszystkich odblokowanych wierzchołków znajdujących się w strefach wierzchołków na ścieżce od \(A\) do \(B\),
• analogicznie – sumę odległości od \(B\) do wszystkich odblokowanych wierzchołków znajdujących się w strefach wierzchołków na ścieżce od \(A\) do \(B\).

Odblokowując wierzchołek \(v_{i+1}\) aktualizujemy drzewa przedziałowe dla wszystkich grubych ścieżek przecinających ścieżkę od \(v_{i+1}\) do korzenia. Jednocześnie obliczamy odległości od wszystkich odblokowanych wierzchołków do \(v_{i+1}\). Szczegóły nietrudno uzupełnić. Ostateczna złożoność rozwiązania to \(O(n + k \log^2 n)\) ze względu na zastosowanie drzew przedziałowych oraz aktualizowanie \(O(\log n)\) grubych ścieżek podczas odblokowywania każdego wierzchołka.