Omówienie zadania Strajki (II etap XXIV OI)

Formalna treść zadania

Mamy dane drzewo o \(n\) wierzchołkach. Początkowo wszystkie wierzchołki są odblokowane. Mamy do obsłużenia \(m\) wydarzeń: każde polegające na odblokowaniu lub zablokowaniu pewnego wierzchołka \(v\). Po każdym zapytaniu należy wypisać liczbę różnych spójnych podgrafów stworzonych z niezablokowanych wierzchołków. Dalej w treści mówiąc o "spójnej składowej" będziemy mieć na myśli spójny podgraf złożony jedynie z niezablokowanych wierzchołków.

Podzadanie 1 – \(n, m \leq 1000\):

Limity w tym zadaniu pozwalają na bezpośrednią symulację procesu. Dla każdego wierzchołka \(v\) utrzymujemy informację, czy jest on zablokowany czy nie. Aby policzyć liczbę spójnych składowych, możemy wykorzystać algorytm DFS wykonany jedynie na niezablokowanych wierzchołkach. Otrzymujemy algorytm działający w złożoności \(O(mn)\).

Podzadanie 2 – \(n, m \leq 500\ 000\) oraz drzewo jest ścieżką

Skoro drzewo jest ścieżką, to możemy jego wierzchołki utożsamiać z punktami na prostej. Wierzchołki w drzewie możemy przenumerować, żeby punktowi \(i\) odpowiadał wierzchołek \(i\) (dla \(1 \leq i \leq n\)) – np. wykonując algorytm DFS na grafie.

Obserwacja: Każdą spójną składową możemy utożsamić z pewnym odcinkiem na prostej.

Zauważmy, że teraz zamiast zliczać liczbę spójnych składowych, wystarczy policzyć liczbę początków odpowiadających im odcinków i wynik będzie taki sam. Takie początki mają ładną charakteryzację. Powiedzmy, że punkt \(1\leq i\leq n\) jest początkiem odcinka. Wówczas zachodzą dwa następujące przypadki:

• \(i = 1\). Wtedy jest to najbardziej skrajny punkt z lewej na prostej (odpowiadający pewnemu liściu w drzewie),
• punkt \(i-1\) jest zablokowany (gdyby nie był, to punkt \(i\) nie mógłby być początkiem).

Zmieniając stan danego punktu \(i\), wystarczy sprawdzić, czy punkty \(i, i+1\) zaczęły lub przestały być początkiem. Złożoność takiego algorytmu to \(O(n+m)\).

Podzadanie 3 – \(n, m \leq 500\ 000\), wierzchołki będą jedynie blokowane

Niech \(A\) będzie zbiorem zablokowanych wierzchołków oraz niech \(\deg(v)\) oznacza stopień wierzchołka \(v\). Skoro wierzchołki będą jedynie blokowane, to zbiór \(A\) będzie się jedynie powiększał. Ponadto niech \(\deg_A(v)\) oznacza liczbę sąsiadów wierzchołka \(v\) należących do zbioru \(A\).

Zauważmy, że zablokowanie pewnego wierzchołka \(v\) zwiększa liczbę spójnych składowych o \(\deg(v)-1-\deg_A(v)\). Wynika to z faktu, że po usunięciu \(v\) każdy niezablokowany sąsiad należy do nowej spójnej składowej (ponieważ drzewo jest acykliczne, a takich sąsiadów jest \(\deg(v)-\deg_A(v)\)).

By policzyć wartość \(\deg(v) - 1 - \deg_A(v)\) możemy przed odpowiadaniem na zapytania policzyć stopnie wszystkich wierzchołków. Następnie, gdy przetwarzamy zapytanie polegające na zablokowaniu \(v\), to iterujemy się po wszystkich sąsiadach wierzchołka \(v\) i zliczamy liczbę zablokowanych sąsiadów (czyli \(\deg_A(v)\)).

Ponieważ w tym podzadaniu każdy wierzchołek zostanie zablokowany maksymalnie raz, to każda krawędź zostanie przejrzana przez powyższy algorytm maksymalnie dwa razy, skąd widzimy, że złożoność w tym podzadaniu wynosi \(O(n+m)\).

Alternatywne rozwiązanie podzadania 3 – Find and Union

Często w tego typu zadaniach usuwanie czy też blokowanie pewnych obiektów jest dużo bardziej skomplikowane niż ich dodawanie. By poradzić sobie z takim problemem, często stosuje się sztuczkę, polegającą na odwróceniu biegu czasu. Dlatego najpierw usuńmy wszystkie wierzchołki podane w zapytaniach, a następnie dodawajmy wierzchołki w odwrotnej kolejności. Wówczas dodanie wierzchołka powoduje dodanie krawędzi między nim a wszystkimi jego niezablokowanymi sąsiadami w grafie. Operację dodawania krawędzi przy jednoczesnym utrzymywaniu aktualnej liczby spójnych składowych możemy zaimplementować z wykorzystaniem algorytmu Find & Union

Pełne rozwiązanie

Zauważmy, że przy odblokowywaniu wierzchołka \(v\) odpowiedź również się zmniejsza o \(\deg(v) - 1 - \deg_A(v)\). Przed odblokowaniem wierzchołek ten ma \(\deg(v)-\deg_A(v)\) niezablokowanych sąsiadów i każdy z nich należy do innej spójnej składowej, zatem dodanie krawędzi między \(v\) i wszystkimi takimi sąsiadami połączy te spójne składowe w jedną spójną, a więc zmniejszy liczbę spójnych składowych o dokładnie \(\deg(v) - 1 - \deg_A(v)\).

Aby szybko poznawać wartość \(\deg_A(v)\) dla każdego wierzchołka \(v\), możemy skorzystać z ukorzenionej struktury drzewa i zauważyć, że wierzchołek \(v\) ma dwa rodzaje sąsiadów: dzieci, które są wierzchołkami w poddrzewie \(v\) (których może być wiele, więc nie chcemy ich przeglądać przy każdym zapytaniu) oraz rodzica wierzchołka \(v\) – wszystkie wierzchołki oprócz korzenia mają dokładnie jednego rodzica, dlatego taki wierzchołek możemy rozpatrzyć oddzielnie.

Zatem dla każdego wierzchołka \(v\) musimy pamiętać informację o jego rodzicu \(p_v\) oraz aktualnej liczbie zablokowanych dzieci \(c_v\). Wtedy operację zablokowania możemy wykonać w czasie stałym: \(deg_A(v)\) to liczba zablokowanych dzieci \(c_v\), z oddzielnym uwzględnieniem stanu \(p_v\). Zmiana stanu \(v\) powoduje, że liczba zablokowanych dzieci rodzica \(v\) (czyli \(c_{p_v}\ \)) się zmienia (zwiększa o \(1\)). Analogicznie działa odblokowywanie wierzchołka. W ten sposób otrzymujemy rozwiązanie działające w złożoności liniowej \(O(n+m)\).

Alternatywne rozwiązanie w złożoności \(O(n \log n)\)

Korzystając z obserwacji, że zablokowanie/odblokowanie wierzchołka \(v\) powoduje, że wynik zmienia się o \(\deg(v)-1-\deg_A(v)\), spróbujmy w alternatywny sposób obliczać \(\deg_A(v)\).

W tym celu znajdźmy kolejność w której przetwarzane są wierzchołki w trakcie algorytmu BFS. Zauważmy, że z konstrukcji algorytmu wynika, że dla każdego \(v\) wszyscy sąsiedzi \(v\) w odległości o \(1\) większej niż \(v\) zostaną rozpatrzone kolejno po sobie.

Zatem gdy znajdziemy taką kolejność wierzchołków dla ukorzenionego drzewa, to wszystkie dzieci każdego wierzchołka będą tworzyć spójny przedział. W ten sposób gdy będziemy w tej kolejności utrzymywać stany wierzchołków (1 – jeśli zablokowane, 0 – jeśli nie), to znalezienie \(\deg_A(v)\) sprowadza się do policzenia sumy na przedziale oraz oddzielnego sprawdzenia stanu rodzica \(v\).

Struktura danych, która pozwala na zmianę wartości stanu w punkcie oraz policzenie sumy na przedziale to drzewo przedziałowe. Z jej wykorzystaniem zadanie możemy rozwiązać w złożoności \(O((n+m)\log n)\).