Omówienie zadania Kontrwywiad (II etap XXXIII OI)

Wstęp

W zadaniu stajemy na czele bajtockiego kontrwywiadu, próbującego powstrzymać szpiegów poruszających się w \(n\)-wierzchołkowym drzewie. Zadanie polega na wybraniu minimalnej liczby wierzchołków do objęcia kwarantanną, tak aby zablokować możliwość spotkania każdej z \(q\) par szpiegów. Każda para porusza się ustaloną, unikalną ścieżką między dwoma miastami. Nasz cel to wybranie zbioru wierzchołków pokrywającego wszystkie te ścieżki.

Przypadek szczególny: Bajtocja jako ścieżka

Zastanówmy się najpierw, jak rozwiązać problem, gdy struktura drzewa jest znacznie prostsza – jest po prostu ścieżką. Wówczas trasa każdej pary szpiegów jest spójnym fragmentem tej ścieżki, czyli przedziałem \([l_i, r_i]\). Problem sprowadza się więc do wybrania minimalnej liczby punktów na odcinku, tak aby każdy z zadanych przedziałów zawierał przynajmniej jeden wybrany punkt.

Zauważmy, że jest to klasyczny problem zachłanny. Rozważmy wszystkie przedziały rosnąco według prawych końców. Jeśli napotkamy przedział, który nie został jeszcze obsłużony (nie zawiera żadnego z wybranych wcześniej punktów), musimy podjąć decyzję. Najlepiej będzie wybrać punkt, który znajduje się jak "najpóźniej" w ramach tego przedziału – czyli jego prawy koniec. Wybór ten jest nie gorszy niż wybranie jednego z wcześniejszych punktów, a dzięki temu maksymalizujemy szansę na pokrycie kolejnych przedziałów, które mogą zaczynać się później, ale wciąż obejmować ten punkt.

Powrót do drzewa

Zauważmy, że podejście ze ścieżki możemy z powodzeniem przenieść na drzewo. Musimy jedynie znaleźć kolejność, w jakiej rozpatrywać ścieżki oraz znaczenie "najpóźniejszego" wierzchołka w ścieżce.

Analogią do "prawego końca" przedziału w drzewie po jego ukorzenieniu jest Najniższy Wspólny Przodek (LCA) danej ścieżki. Podobnie jak na odcinku przetwarzaliśmy przedziały od lewej do prawej (według końców), tak w drzewie naturalną kolejnością jest przeglądanie od dołu do góry – czyli post-order. Przetwarzając wierzchołek \(v\), rozpatrujemy wszystkie ścieżki, dla których \(v\) jest LCA. Te ścieżki "kończą się" (w sensie wysokości w drzewie) właśnie w \(v\).

Strategia zachłanna w drzewie

Kierując się naszą analogią, dochodzimy do prostej strategii. Przeglądamy nasze drzewo od dołu, w kolejności post-order. Będąc w wierzchołku \(v\), sprawdzamy wszystkie pary szpiegów, których trasy mają swoje LCA właśnie tutaj. Jeśli któraś z tych par wciąż może się spotkać (czyli na ich trasie nie ustanowiono jeszcze kwarantanny w żadnym z wierzchołków położonych niżej w drzewie), jesteśmy zmuszeni do zablokowania pewnego wierzchołka. Musimy wybrać pewien wierzchołek z tej trasy do objęcia kwarantanną. Który wybrać?

Oczywiście wierzchołek \(v\). Analogicznie do przypadku ze ścieżką - wybór \(v\) jest optymalny, ponieważ leży on najwyżej. Jeśli jakakolwiek inna, nierozpatrzona jeszcze para szpiegów ma trasę przecinającą obecną, to musi ona przechodzić przez wierzchołek \(v\) lub któryś z wierzchołków leżących powyżej niego. Wybierając \(v\), dajemy sobie szansę na zablokowanie również tych przyszłych tras. Wybór wierzchołka położonego głębiej byłby nie lepszy, gdyż nie pomógłby w zablokowaniu tras przechodzących przez \(v\), które nie schodzą do tego konkretnego głębszego wierzchołka.

Rozwiązanie wzorcowe

Kluczem do wydajności jest szybkie sprawdzanie, czy dana para szpiegów ma już zablokowaną drogę. Naiwna weryfikacja dla każdej pary byłaby zbyt wolna. Z pomocą przychodzi nam ponownie numerowanie wierzchołków w kolejności pre-order i post-order.

Każdemu wierzchołkowi możemy przypisać moment wejścia do niego (\(in\)) oraz wyjścia z niego (\(out\)). Gdy decydujemy się objąć kwarantanną wierzchołek \(v\), zaznaczamy to w naszej strukturze danych (np. drzewie przedziałowym), dodając wartość \(1\) w punkcie \(in[v]\) oraz \(-1\) w punkcie \(out[v]\). Działa to jak stawianie nawiasów: otwieramy blokadę przy wejściu do poddrzewa i zamykamy przy wyjściu, tak aby informacja ta nie dotyczyła zapytań wierzchołków znajdujących się gdzie indziej w grafie.

Aby sprawdzić, czy występuje zablokowany wierzchołek na ścieżce pomiędzy wierzchołkami \(a\) i \(b\), najpierw rozbijemy ścieżkę na dwie części - z \(a\) do \(v\) i z \(b\) do \(v\) (gdzie \(v\) jest LCA wierzchołków \(a\) i \(b\)). Następnie, dzięki powyżej opisanej strukturze, dla fragmentu ścieżki z \(u\) do \(v\), gdzie \(u \in \{a, b\}\) pytamy o sumę wartości na przedziale numerów od \(in[v]\) do \(in[u]\). Jeśli na tej ścieżce znajduje się jakiś zablokowany wierzchołek, to nasz przedział obejmie tylko jego "nawias otwierający" (+1), zaś nie obejmie "zamykającego" (-1), co da wynik dodatni.

Sprawdzamy więc, czy dla którejś ze ścieżek z \(a\) do \(v\) i z \(b\) do \(v\) wynik jest dodatni - jeżeli jest, to znaczy, że ścieżka ta już była zablokowana. W przeciwnym wypadku musimy wstawić blokadę w wierzchołku \(v\). Takie podejście pozwala nam osiągnąć złożoność \(O((n+q) \log n)\), co w zupełności wystarcza do zdobycia kompletu punktów.