Omówienie zadania Gang biciaków (I etap XXVIII OI)

Dane jest ukorzenione drzewo o \(n\) wierzchołkach, w którym każda krawędź jest pomalowana na jeden z \(m\) kolorów. Należy obsłużyć \(z\) zapytań. Każde z nich jest jednego z następujących typów:

• typu B: zmień kolor jakiejś krawędzi,

• typu Z: dla danego wierzchołka \(v\), policz różne kolory na ścieżce z korzenia do \(v\).

Podzadania 1 i 2

Każde zapytanie Z obsługujemy niezależnie w czasie \(O(n)\). Najpierw przeszukujemy drzewo, poszukując ścieżki z korzenia do wierzchołka \(v\). Następnie zapisujemy sobie wszystkie kolory krawędzi na tej ścieżce (albo w strukturze set – złożoność \(O(\log m)\) na dodanie koloru, albo w tablicy długości \(m\) – złożoność \(O(1)\)).

Czas działania to \(O(zn\log m)\) dla set lub \(O(zn + m)\) dla tablicy. Przy czym po każdym zapytaniu czyścimy tablicę, przechodząc jeszcze raz po ścieżce do \(v\) i usuwając tylko kolory występujące na ścieżce (żeby czyszczenie trwało czas \(O(n)\), a nie \(O(m)\)).

Podzadanie 3

Jeśli nie mamy zapytań Z, to możemy jednym przejściem algorytmu DFS rozważyć wszystkie wierzchołki \(v\) z zapytań. Potrzebujemy struktury danych multizbiór, która umożliwia: dodanie koloru, usunięcie koloru i zwrócenie liczby różnych kolorów.

Podczas algorytmu DFS:

• gdy idziemy krawędzią w dół, to dodajemy jej kolor do multizbioru,

• gdy wracamy krawędzią w górę, to usuwamy jej kolor z multizbioru,

• gdy jesteśmy w wierzchołku \(v\), to zapisujemy liczbę różnych krawędzi w multizbiorze jako odpowiedź na zapytanie o ten wierzchołek.

Multizbiór możemy zaimplementować jako tablicę \(t[1..m]\), gdzie \(t[i]\) oznacza ile razy występuje kolor \(i\), plus licznik niezerowych wartości w tej tablicy. Dodanie koloru \(i\) zwiększa \(t[i]\) o 1, a ponadto zwiększa licznik, jeśli początkowo było \(t[i]=0\). Usunięcie koloru \(i\) zmniejsza \(t[i]\) o 1, a ponadto zmniejsza licznik, jeśli początkowo było \(t[i]=1\). Dzięki temu wszystkie operacje na multizbiorze wykonujemy w czasie \(O(1)\).

Czas działania to \(O(n + z + m)\).

Pełne rozwiązanie

W podzadaniu 3 algorytm DFS przechodzi drzewo ścieżką Eulera długości \(2(n-1)\). Idąc krawędzią w dół dajemy operację ,,dodaj kolor”, a idąc krawędzią w górę dajemy operację ,,usuń kolor”. Widać, że odpowiedź dla ścieżki prostej od korzenia do wierzchołka \(v\) będzie liczbą różnych kolorów w multizbiorze po zastosowaniu wszystkich operacji z prefiksu ścieżki Eulera do wierzchołka \(v\).

Teraz dzielimy ścieżkę Eulera na \(O(\sqrt n)\) kubełków długości \(O(\sqrt n)\) i do każdego kubełka wrzucamy zapytania Z, które się w nim kończą.

Kubełki rozpatrujemy niezależnie. Dla ustalonego kubełka najpierw wykonujemy operacje ze ścieżki Eulera do początku kubełka. Trzymamy też długość aktualnie rozważanego prefiksu ścieżki Eulera (początkowo jest ustawiona na początek kubełka) oraz multizbiór wartości na prefiksie.

Teraz chronologicznie przechodzimy po następujących zapytaniach:

• Wszystkich zapytaniach B z wejścia: dla każdego z nich zmieniamy dwie wartości na ścieżce Eulera (dla krawędzi w górę i w dół). Dla wartości, które mieszczą się w rozważanym prefiksie, również uaktualniamy je w multizbiorze (co da co najwyżej cztery operacje dodaj/usuń).

• I równocześnie zapytaniach Z z kubełka: tutaj uaktualniamy długość rozważanego prefiksu, aby kończył się na wierzchołku \(v\) z zapytania. To wymaga do \(O(\sqrt n)\) operacji dodaj/usuń na multizbiorze. Odpowiedzią na zapytanie jest aktualny licznik multizbioru.

Wszystkie zapytania typu B z jednego kubełka zrealizujemy w czasie \(O(z)\), więc dla wszystkich kubełków to będzie \(O(z\sqrt{n})\). Również wszystkie zapytania typu Z zrealizujemy w czasie \(O(z\sqrt{n})\).

Przygotowanie ścieżki Eulera to dodatkowy czas \(O(n)\), sortowanie zapytań to czas \(O(z\log z)\), a przygotowanie multizbioru czas \(O(m)\). Ostatecznie złożoność czasowa to \(O((n+z)^{3/2} + m)\).

Alternatywnie można o tym rozwiązaniu myśleć jak o algorytmie Mo na drzewie, przy czym, dość nietypowo, jednym z wymiarów przestrzeni stanów w algorytmie Mo jest numer zapytania. Innymi słowy, wyobrażamy sobie, że na wejściu dostajemy pokolorowane drzewo oraz ciąg zmian kolorów krawędzi tego drzewa i mamy odpowiadać na zapytania postaci ,,po \(t\) przekolorowaniach, ile jest różnych kolorów na ścieżce z korzenia do \(v\)”?