Wiosenne porządki

Mając dane drzewo $n$-wierzchołkowe $(3\le n\le {10}^5)$ oraz $q$ operacji $(1\le q\le {10}^5)$, należy po każdej operacji wypisać minimalny koszt wyczyszczenia drzewa. Każda operacja jest wykonywana niezależnie (czyli na niezmienionym drzewie) i polega na dodaniu dodatkowych synów do wybranych wierzchołków oryginalnego drzewa (suma ilości dodanych synów po wszystkich operacjach nie przekracza ${10}^5$).

Podzadanie 2

Ograniczenia: zachodzi $q=1$, istnieje krawędź między wierzchołkiem $1$ oraz $i$ dla $2\le i\le n$ oraz nie są dodawane wierzchołki do wierzchołka $1$.

Po dodaniu nowych liści, jeżeli istnieje wierzchołek posiadający co najmniej dwa liście, to można liście zachłannie między sobą parować (przy czym trzeba uważać na to, aby nie sparować ze sobą wszystkich liści, które są synami wierzchołka niebędącego korzeniem). Po tym można zauważyć, że nieważne jak sparujemy wierzchołki, to ścieżka między każdą parą wierzchołków przechodzi przez korzeń, więc wystarczy tylko rozpatrywać sumę odległości liści do korzenia.

Parzyste i nieparzyste wierzchołki

Można udowodnić, że w rozwiązaniu optymalnym, każda krawędź zostanie wyczyszczona co najwyżej dwukrotnie (szkic dowodu jest następujący -- jeżeli istnieje taka krawędź, która jest wyczyszczona co najmniej trzykrotnie, to zamiast łączyć ze sobą pewną ilość par wierzchołków po różnych stronach krawędzi, lepiej jest złączyć takie, co są po tej samej stronie).

Należy więc zminimalizować liczbę krawędzi drzewa, które zostaną wyczyszczone dwukrotnie.

Dla wygody ukorzeńmy sobie drzewo w wierzchołku niebędącym liściem. Niech $parent(v)$ będzie ojcem wierzchołka $v$. Niech $v$ będzie nazwany parzystym, jeżeli w jego poddrzewie jest parzyście wiele liści (analogicznie nieparzysty).

Dana krawędź od $v$ do $parent(v)$ na pewno będzie musiała być dwukrotnie czyszczona, gdy $v$ jest parzystym wierzchołkiem. Można też wykazać, że jeżeli $v$ jest nieparzysty, to zawsze można ją jednokrotnie czyścić.

Z tego wynika, że odpowiedzią dla dowolnego drzewa jest $n+|P|-2$, gdzie $P$ to zbiór parzystych wierzchołków i można to obliczyć w $O(n)$ dla $n$-wierzchołkowego drzewa poprzez pojedynczego DFS-a.

Jeżeli taki algorytm zostanie użyty dla każdego zapytania, to otrzyma się rozwiązanie w złożoności $O(nq+\sum D_i)$, gdzie $D_i$ to liczba dodanych liści w $i$-tym zapytaniu.

Podzadanie 4

Dla $n\le 20000,q\le 300$ można użyć powyższego algorytmu.

Podzadanie 5 oraz 6

Gdy jest dodawany liść do wierzchołka $v$, parzystość wierzchołków $v,parent(v),parent(parent(v)),\dots$ się zmienia. Podejściem używanym w obu podzadaniach jest utrzymywanie parzystości wierzchołków oraz sumaryczną liczbę parzystych wierzchołków.

Zależnie od podzadania:

• w podzadaniu 5 podane drzewo jest pełnym binarnym drzewem, więc dla każdego nowego liścia można w pętli zmienić wszystkie te wierzchołki, gdyż głębokość drzewa wynosi $O(\log n)$. Po operacji można analogicznie cofnąć dodanie tych liści.
• w podzadaniu 6 każda operacja dodaje dokładnie jeden liść, więc można spreprocessować liczbę wierzchołków parzystych i nieparzystych od korzenia do $v$ dla każdego wierzchołka $v$, dzięki temu można obliczyć w jaki sposób zmieni się wartość $D$ w czasie stałym dla jednej operacji.

Podzadanie 7 -- rozwiązanie z drzewem wirtualnym

Zauważmy, że gdy dodamy liść do wierzchołka $v$ oraz do wierzchołka $u$, to wierzchołek $LCA(v,u)$ nie zmieni parzystości (ani wyższe wierzchołki na ścieżce do korzenia).

Niech zbiór $L_i$ to zbiór wierzchołków, które w danej operacji mają dodanego co najmniej jednego nowego syna. Niech $W(L_i)$ będzie zbiorem wierzchołków drzewa wirtualnego zdefiniowanego przez zbiór $L_i$, czyli $W(L_i)$ składa się ze zbioru $L_i$ oraz $LCA$ każdej pary wierzchołków $L_i$. Można udowodnić, że $|W(L_i)|=min(n,2D_i-1)$ i można go skonstruować po prostu biorąc wszystkie wierzchołki $L_i$ i biorąc $LCA$ kolejnych dwóch wierzchołków ciągu $L_i$ posortowanego według numerów preorder całego drzewa. Mając zbiór $W(L_i)$, można teraz skonstruować drzewo wirtualne $W_i$, czyli takie drzewo o zbiorze wierzchołków $W(L_i)$, gdzie $v$ jest przodkiem $u$ w tym drzewie, jeżeli $v$ jest przodkiem $u$ w oryginalnym drzewie.

W drzewie $W_i$ dla każdego wierzchołka policzmy liczbę nowo dodanych liści w jego poddrzewie. Jeżeli dla wierzchołka $v\in W(L_i)$ ta liczba jest nieparzysta, to wszystkie wierzchołki w oryginalnym drzewie na ścieżce od $v$ do $parent(v,W_i)$ (ale nie wliczając $parent(v,W_i)$) zmienią swoją parzystość. Jeżeli ta liczba jest parzysta, nic się nie zmienia.

Zadanie więc zostało sprowadzone do obliczenia wyniku po zmienieniu parzystości $O(D_i)$ rozłącznych ścieżek w oryginalnym drzewie. Korzystając z podejścia z podzadania 6, w $O(1)$ można policzyć zmianę w liczbie parzystych wierzchołków po zmienieniu parzystości wierzchołków na wybranej ścieżce (korzystając z podejścia, że ścieżka od $v$ do jego przodka $u$ to jest ścieżka od $v$ do korzenia, „odjąć” ścieżka od ojca $u$ do korzenia).

Podzadanie 7 -- rozwiązanie z HLD

Operacje z podzadania 6 można rozwiązać w $O(D_i{\log }^{2}n)$ za pomocą heavy-light decomposition z operacjami zmienienia stanu wierzchołków (parzysty lub nieparzysty) na wybranej ścieżce oraz policzenia liczby wierzchołków z danym stanem.

Podzadanie 7 -- rozwiązanie z mniejszym do większego

Dla każdego wierzchołka spreprocessujmy indeksy operacji, które sprawią, że w tym wierzchołku zostanie doczepiony nowy syn. Wtedy, DFS-em od liści do korzenia można sparować niesparowane liście. Takie niesparowane liście (identyfikowane poprzez numer oryginalnego liścia lub numer operacji dodającej tego liścia) można trzymać w secie, a w każdym wierzchołku w tym DFS-ie należy w pewien sposób złączyć takie dwa zbiory.

Jeżeli spotkamy dwóch synów mających niesparowany wierzchołek dodany przez taką samą operację, to aktualny wierzchołek jest LCA tych dwóch liści, więc można odpowiednio policzyć zmianę w liczbie parzystych wierzchołków.

Taki algorytm daje tylko zmianę wyniku w porównaniu do oryginalnego drzewa. Należy więc jeszcze policzyć wynik oryginalnego drzewa, bez żadnych operacji.

Żeby zachować złożoność mniejszą niż kwadratowa, można zawsze łączyć mniejszy zbiór do większego (co jest potocznie nazywane „metodą mniejszy do większego”), otrzymując złożoność $O((n+\sum D_i)\log (n+\sum D_i)+q)$.