Omówienie zadania Bieg na orientację (eliminacje do IOI 2020, dzień 3)

Formalna treść zadania

Dane jest drzewo nieważone o \(n \leq 300\ 000\) wierzchołkach. Należy odpowiedzieć na \(q \leq 200\ 000\) niezależnych zapytań. Każde z nich jest trójką liczb nieujemnych \(d_{12}, d_{23}, d_{13}\). Dla każdej takiej trójki należy odpowiedzieć, czy istnieją takie trzy wierzchołki \(v_1, v_2, v_3\), że odległości między nimi spełniają warunki \(d(v_1, v_2) = d_{12}\), \(d(v_2, v_3) = d_{23}\) oraz \(d(v_1, v_3) = d_{13}\), lub stwierdzić, że takie wierzchołki nie istnieją. Odległość między dwoma wierzchołkami \(u, v\) to liczba krawędzi na najkrótszej ścieżce między nimi, oznaczana przez \(d(u, v)\).

Podzadanie 1 – \(n \leq 100\)

Możemy wykonać preprocessing wszystkich par odległości (przykładowo algorytmem DFS bądź BFS) oraz zapamiętać dla każdej trójki liczb, czy występuje ona jako trójka odległości między pewnymi trzema wierzchołkami w drzewie. Dzięki temu jesteśmy w stanie uzyskać rozwiązanie w złożoności \(O(n^3 + q)\).

Podzadanie 2 – \(n, q \leq 1000\)

Obserwacja: dla dowolnych trzech wierzchołków \(v_1, v_2, v_3\) istnieje wierzchołek \(x\) leżący na każdej z trzech ścieżek pomiędzy parami wierzchołków \((v_1, v_2)\), \((v_2, v_3)\) oraz \((v_1, v_3)\). Taki wierzchołek \(x\) nazwijmy „środkowym” wierzchołkiem. Analogiczna obserwacja pojawiła się w zadaniu „Hotele” z XXI OI.

Dowód: Dla danej trójki wierzchołków \(v_1, v_2, v_3\) określmy wierzchołek \(x\) jako pierwszy wierzchołek ze ścieżki \(v_3 \leadsto v_1\), który znajduje się także na ścieżce \(v_2 \leadsto v_1\) (musi taki istnieć, bo przykładowo \(v_1\) spełnia ten warunek). Oczywiście istnieje wtedy ścieżka \(v_2 \leadsto x \leadsto v_3\), a skoro taka ścieżka w drzewie jest unikalna, to \(x\) również leży na ścieżce \(v_2 \leadsto v_3\).

W ten sposób uzyskujemy, że:

• \(d(x, v_1) + d(x, v_2) = d_{12}\)
• \(d(x, v_2) + d(x, v_3) = d_{23}\)
• \(d(x, v_1) + d(x, v_3) = d_{13}\)

Po dodaniu nierówności stronami dostajemy, że \(2(d(x, v_1) + d(x, v_2) + d(x, v_3)) = d_{12} + d_{23} + d_{13}\), zatem warunkiem koniecznym istnienia całkowitoliczbowego rozwiązania jest \(2 \mid d_{12} + d_{23} + d_{13}\). Ponadto, by rozwiązania były nieujemne, odległości \(d_{i, j}\) muszą spełniać nierówność trójkąta. Przykładowo, rozważmy wyrażenie: \[d_{12} + d_{23} - d_{13} = d(x, v_1) + d(x, v_2) + d(x, v_2) + d(x, v_3) - d(x, v_1) - d(x, v_3) = 2d(x, v_2) \geq 0.\] Otrzymujemy zatem drugi warunek konieczny – wszystkie \(d_{i, j}\) muszą spełniać nierówność trójkąta. Są to również warunki wystarczające, by rozwiązać powyższy układ równań i znaleźć wartości \(d(x, v_1), d(x, v_2), d(x, v_3)\).

Będziemy dla każdego zapytania przeglądać wszystkie wierzchołki drzewa i sprawdzać, czy są one dobrymi kandydatami na \(x\). Jeśli dla pewnego \(i \in \{1, 2, 3 \}\) zachodzi \(d(x, v_i) = 0\), to wystarczy wziąć \(v_i = x\). Zatem od tej pory dla ułatwienia rozważań załóżmy, że żadna z odległości od \(x\) nie jest równa \(0\) . Wtedy wierzchołki \(v_1, v_2, v_3\) muszą znajdować się w różnych poddrzewach wierzchołka \(x\) na głębokościach odpowiednio \(d(x, v_1), d(x, v_2), d(x, v_3)\).

Przed odpowiadaniem na zapytania policzmy zatem trzy najdłuższe ścieżki wychodzące z każdego wierzchołka. Powiedzmy, że drzewo jest ukorzenione w wierzchołku \(r\). W tak ukorzenionym drzewie policzmy dla każdego wierzchołka \(u\) jego głębokość, rodzica oraz informację, do jakiego poddrzewa dziecka \(r\) wierzchołek \(u\) należy. Wybieramy trzy wierzchołki \(u_{r, 1}, u_{r, 2}, u_{r, 3}\) o największej głębokości znajdujące się w różnych poddrzewach – niech te głębokości to \(h_{r, 1}\geq h_{r, 2} \geq h_{r, 3}\) (być może niektóre równe \(0\) jeśli są mniej niż trzy różne poddrzewa). Dzięki informacji o rodzicach jesteśmy w stanie wyznaczyć ciąg wierzchołków na takich trzech najdłuższych ścieżkach dla każdej możliwości \(r\).

Wróćmy do odpowiadania na zapytania. Możemy przeglądać wszystkich kandydatów na wierzchołek „środkowy” \(x\). Załóżmy bez straty ogólności, że \(d(x, v_1) \geq d(x, v_2) \geq d(x, v_3)\). Zauważmy, że jeśli istnieje pewne poprawne przyporządkowanie wierzchołków \(v_i\) dla \(i \in \{1, 2, 3\}\) do poddrzew wierzchołka \(x\), to w szczególności istnieje takie w którym \(v_1\) przyporządkowujemy poddrzewo o maksymalnej głębokości \(h_{x, 1}\), \(v_2\) – do poddrzewa o głębokości \(h_{x, 2}\), zaś \(v_3\) – do \(h_{x, 3}\).

Zatem \(x\) jest dobrym „środkowym” wierzchołkiem dokładnie wtedy, gdy \(h_1 \geq d(x, v_1), h_2 \geq d(x, v_2), h_3 \geq d(x, v_3).\) Po znalezieniu dobrego kandydata na \(x\) w czasie \(O(n)\) odzyskujemy wierzchołki \(v_1, v_2, v_3\) z wcześniej policzonych trzech najgłębszych ścieżek w czasie stałym.

Preprocessing ścieżek wykonujemy w złożoności \(O(n^2)\), a na każde zapytanie odpowiadamy w złożoności \(O(n)\), zatem uzyskujemy rozwiązanie działające w czasie \(O(n^2 + nq)\). Powyższa obserwacja z istnieniem „środkowego” wierzchołka \(x\) okaże się jednak kluczowa przy pełnym rozwiązaniu zadania.

Podzadanie 3 – \(q \leq 100\)

Spróbujmy usprawnić najwolniejszą część rozwiązania z poprzedniego zadania – liczenie \(h_{x, 1}, h_{x, 2}, h_{x, 3}\). Przydatne będzie w tym celu rozważenie programowania dynamicznego.

Ukorzeńmy drzewo dowolnie, np. w wierzchołku \(1\). Najpierw spróbujmy policzyć trzy najdłuższe ścieżki wychodzące z każdego wierzchołka do jego poddrzewa. W takim razie niech \(\texttt{dp}[v][i]\) (dla \(0\leq i\leq 2\)) oznacza \(i+1\)-szą najdłuższą ścieżkę w poddrzewie \(v\) o jednym końcu w wierzchołku \(v\), przy czym te trzy ścieżki należą do trzech różnych poddrzew \(v\). Ponieważ będziemy musieli jeszcze odtworzyć wierzchołki \(v_1, v_2, v_3\), to \(\texttt{dp}[v][i]\) będzie dodatkowo utrzymywać informację o drugim końcu tej ścieżki. Takie programowanie dynamiczne jesteśmy w stanie policzyć w czasie \(O(n)\) podczas wykonywania algorytmu DFS. Gdy w trakcie przeszukiwania grafu jesteśmy w liściu \(v\), to \(\texttt{dp}[v][0] = (0, v)\), a pozostałe wartości \(\texttt{dp}[v][1], \texttt{dp}[v][2]\) ustawiamy na \((-\infty, -\infty)\). W przeciwnym przypadku jesteśmy w stanie policzyć wartości \(\texttt{dp}[v][i]\) na podstawie wartości \(\texttt{dp}[u][0]\) dla dzieci \(u\) – wybierając trzy największe wartości \(\texttt{dp}[u][0]\) dla różnych dzieci \(u\) i zwiększając liczbę krawędzi na ścieżce \(\texttt{dp}[v][i]\) o \(1\), ponieważ używamy wtedy dodatkowej krawędzi z \(u\) do \(v\).

Takie rozwiązanie oczywiście nie znajduje trzech najdłuższych ścieżek wychodzących z wierzchołka \(v\), ponieważ szukamy ich jedynie w poddrzewie \(v\). Może się jednak okazać, że jedna z trzech optymalnych ścieżek wychodzi z \(v\) do naddrzewa wierzchołka \(v\) (czyli używa krawędzi do rodzica \(v\)). By to naprawić, policzmy jeszcze \(\texttt{DP}[v]\) – liczbę krawędzi oraz drugi koniec ścieżki, która kończy się w wierzchołku \(v\) oraz używa krawędzi z \(v\) do rodzica \(v\). Wykonując drugie przeszukiwanie w głąb jesteśmy w stanie w czasie liniowym obliczyć \(\texttt{DP}[v]\) dla każdego wierzchołka \(v\). Ustalmy \(v\) oraz niech rodzicem tego wierzchołka będzie wierzchołek \(p\). Wówczas zachodzą dwa przypadki:

• ścieżka wychodząca z \(v\) przez \(p\) „skręca”, zatem w tym przypadku wystarczy znaleźć najdłuższą ścieżkę postaci \(v \to p \to u \to \dots\), gdzie \(u\) jest dzieckiem wierzchołka \(p\) innym niż \(v\). By efektywnie liczyć taką wartość, możemy będąc w wierzchołku \(v\) spreprocessować maksima prefiksowe i sufiksowe \(\texttt{dp}[u][0]\) dla wszystkich dzieci \(p\) przed liczeniem \(\texttt{DP}\).
• ta ścieżka idzie dalej w górę drzewa z wierzchołka \(p\) – wówczas najdłuższą taką ścieżkę już policzyliśmy i jest to \(\texttt{DP}[p]\).

Alternatywnie możemy o tym myśleć w ten sposób, że wierzchołek \(p\) stał się tymczasowo „nowym” korzeniem naszego drzewa. Technika polegająca na liczeniu odpowiedzi dla wielu korzeni nazywa się \(\textit{rerooting}\) i można o niej poczytać więcej np. tutaj.

Liczenie \(\texttt{DP}[v]\) również wykonujemy w czasie liniowym. Wówczas dla każdego wierzchołka \(v\) mamy maksymalnie cztery optymalne ścieżki i jesteśmy w stanie w czasie stałym odczytać wartości \(\texttt{DP}[v]\) oraz \(\texttt{dp}[v][0], \texttt{dp}[v][1], \texttt{dp}[v][2]\), w szczególności wierzchołki będące drugimi końcami tych ścieżek. Wówczas jesteśmy w stanie w czasie stałym sprawdzić, czy \(v\) jest dobrym kandydatem na „środkowy” wierzchołek i jeśli jest, to w czasie liniowym (podobnie jak w poprzednim podzadaniu) odtworzyć wierzchołki \(v_1, v_2, v_3\). Złożoność takiego rozwiązania to \(O(n + nq)\).

Pełne rozwiązanie

Bazując na algorytmie opisanym w podzadaniu 3 umiemy znaleźć dla każdego wierzchołka \(v\) głębokości \(h_{v, 1}, h_{v, 2}, h_{v, 3}\) oraz odpowiadające im końce ścieżek \(u_{v, 1}, u_{v, 2}, u_{v, 3}\) w złożoności \(O(n)\). Pozostało tylko zoptymalizować znalezienie takiego wierzchołka „środkowego” \(x\), że \(h_{x, 1} \geq d(x, v_1), h_{x, 2} \geq d(x, v_2)\) oraz \(h_{x, 3} \geq d(x, v_3)\).

Gdy mamy do czynienia z takimi nierównościami, to zazwyczaj warto podejść do takiego problemu geometrycznie. Załóżmy póki co, że musimy znaleźć \(x\) spełniający jedynie dwie z nierówności: \(h_{x, 1} \geq d(x, v_1), h_{x, 2} \geq d(x, v_2)\). Wtedy, jeśli wartości utożsamimy z punktami \(P_x= (h_{x, 1}, h_{x, 2}\)) oraz \(Q_x = (d(x, v_1), d(x, v_2))\) na płaszczyźnie, to nasze nierówności sprowadzają się do tego, że punkt \(P_x\) powinien znajdować się w prawej górnej ćwiartce płaszczyzny względem punktu \(Q_x\). Wówczas takie sprawdzenie jesteśmy w stanie wykonać techniką zamiatania.

Żeby uogólnić to myślenie do naszego problemu, umieśćmy na płaszczyźnie punkt \((h_{v, 1}, h_{v, 2})\) o wadze \(h_{v, 3}\) dla każdego wierzchołka \(v\) w drzewie. Wówczas każde zapytanie postaci \(d(x, v_1) \geq d(x, v_2) \geq d(x, v_3)\) jest równoważne ze znalezieniem w ćwiartce płaszczyzny \([d(x, v_1), \infty) \times [d(x, v_2), \infty) \) jakiegokolwiek punktu o wadze równej przynajmniej \(d(x, v_3)\). Możemy zatem posortować punkty nierosnąco – najpierw względem drugiej współrzędnej, a następnie pierwszej, priorytetyzując głębokości policzone w drzewie ponad wartości zapytań. Sprawdzenie, czy taki punkt istnieje jest równoważne ze znalezieniem maksimum na przedziale \([d(x, v_1), \infty)\). Struktura danych, która pozwala szybko wykonywać te operacje, to drzewo przedziałowe utrzymujące maksimum na przedziale. Ponadto oprócz wagi możemy na drzewie trzymać parę \((h_{x, 3}, x)\), żeby jednocześnie móc odzyskiwać wartość „środkowego” wierzchołka \(x\).

W ten sposób dla każdego zapytania znaleźliśmy wierzchołek „środkowy” \(x\). To jednak nie wszystko, ponieważ musimy jeszcze odtworzyć wierzchołki \(v_1, v_2, v_3\). Mamy jednak końce trzech najdłuższych ścieżek wychodzące z wierzchołka \(x\) do wierzchołków \(u_{x, 1}, u_{x, 2}, u_{x, 3}\), policzone w trakcie liczenia programowania dynamicznego. Musimy zatem odtworzyć wierzchołek na ścieżce od \(x\) do \(u_{x, i}\) w odległości \(d(x, v_i)\) od wierzchołka \(x\) dla \(i \in \{1, 2, 3\}\). W tego typu problemach technika jump-pointerów zazwyczaj jest bardzo przydatna. Tak też i będzie w tym przypadku. Niech \(D = d(x, u_i)\) oraz \(L = lca(x, u_i)\) będzie najniższym wspólnym przodkiem wierzchołków \(x\) oraz \(u_i\). Jeśli \(d(x, L) \leq d(x, v_i)\), to wierzchołek \(v_i\) jest przodkiem wierzchołka \(x\) na głębokości o \(d(x, v_i)\) mniejszej. W przeciwnym przypadku \(v_i\) jest przodkiem wierzchołka \(u_i\) na głębokości o \(D - d(x, v_i)\) mniejszej. Takich przodków możemy wyznaczać stosując technikę jump-pointerów.

Otrzymujemy rozwiązanie działające w złożoności \(O((n+q)\log(n+q))\) ze względu na konieczność zastosowania drzewa przedziałowego, sortowania danych oraz wykonania techniki jump-pointerów na drzewie. Takie rozwiązanie pozwalało na uzyskanie maksymalnej liczby punktów na zawodach.