Omówienie zadania Agenci (II etap XXIX OI)

Na początek zróbmy dość oczywistą obserwację, że kolejność, w jakiej przeplatamy ruchy różnych agentów, nie ma znaczenia. Wobec tego możemy założyć, że najpierw swoje wszystkie ruchy wykonuje pierwszy agent, potem swoje wszystkie ruchy wykonuje agent drugi itd.

Podzadanie 4 (\(k=1\))

Na początek zajmiemy się podzadaniem, w którym co prawda drzewo może być maksymalnego rozmiaru, ale mamy tylko jednego agenta. Standardowo ukorzeńmy nasze drzewo i zróbmy to w wierzchołku, w którym jest ten jedyny agent.

Załóżmy na chwilę, że agent musi odwiedzić wszystkie miasta i wrócić do korzenia drzewa. Jednym ze sposobów na zrobienie tego jest obejście drzewa ścieżką Eulera. W ten sposób agent przejdzie dwa razy każdą z \(n-1\) krawędzi, raz w dół drzewa, a raz w górę drzewa, zatem przejście będzie wymagało \(2(n-1)\) dni. Zauważmy, że rzeczywiście jest to minimalna liczba dni, ponieważ do każdego poddrzewa musimy wejść krawędzią, aby odwiedzić zawarte w nim wierzchołki, a potem z niego wyjść, aby odwiedzić resztę drzewa lub powrócić do korzenia.

Jednak w naszym zadaniu agent nie musi wracać do korzenia i może zakończyć swój spacer od razu po odwiedzeniu ostatniego miasta. Opłaca nam się skończyć w mieście, które jest położone jak najdalej od korzenia: jeżeli jego odległość od korzenia będzie równa \(\ell\), to wtedy będziemy potrzebowali \(2(n-1) - \ell\) dni. Wystarczy nam zatem znaleźć najgłębszy liść w ukorzenionym drzewie, albo inaczej głębokość tego drzewa.

To możemy zrobić w czasie \(O(n)\) za pomocą jednego przejścia DFS po naszym drzewie, w którym będziemy pamiętać głębokość aktualnie odwiedzanego wierzchołka. Możemy też na to spojrzeć jak na bardzo proste programowanie dynamiczne na drzewie, w którym, zaczynając od liści i idąc w górę korzenia, obliczamy głębokości kolejnych poddrzew jako \(1\) plus maksimum z głębokości poddrzew zaczepionych w dzieciach.

Podzadanie 5 (\(k=2\))

Narysujmy sobie przykładowe drzewo z dwoma agentami i przykładowe trasy, którymi mogą się poruszać, aby odwiedzić wszystkie miasta. Zauważmy, że jedna krawędź na ścieżce pomiędzy wierzchołkami, z których startują agenci, nie będzie odwiedzona przez żadnego z nich. Jest tak dlatego, że część miast na tej ścieżce będzie odwiedzonych przez jednego agenta, a część miast przez drugiego. Krawędź łącząca miasto odwiedzone przez różnych agentów nie będzie mogła być odwiedzona, ponieważ jeżeli agent odwiedza krawędź, to odwiedza też oba miasta, które ona łączy.

Jeżeli zatem usuniemy tę krawędź z drzewa, to rozpadnie się ono na dwie spójne składowe. Każda z nich będzie drzewem z jednym agentem. Wobec tego optymalnie będzie w każdej z nich zastosować algorytm dla przypadku \(k = 1\). W każdej składowej znajdujemy wierzchołek najdalej położony od agenta (oznaczmy odległości tych wierzchołków od agentów przez \(\ell_1\) i \(\ell_2\)). Odpowiedzią będzie \(2 (n - 2) + \ell_1 + \ell_2\), jednak wynik istotnie zależy od krawędzi, którą usuniemy.

Łatwo zatem podać rozwiązanie \(O(n^2)\) dla tego podzadania. Dla każdego wyboru krawędzi do usunięcia ze ścieżki pomiędzy agentami rozważmy w czasie \(O(n)\) dwa przypadki z \(k = 1\).

Można całą złożoność poprawić do \(O(n)\), jeśli zrobi się programowanie dynamiczne, które dla ukorzenionego drzewa policzy nam głębokości wszystkich ukorzenionych poddrzew oraz kawałków drzew, które pozostają po usunięciu takich poddrzew. Po szczegóły odsyłam do omówienia zadania Modernizacja autostrady opisanego w niebieskiej książeczce XXII Olimpiady Informatycznej.

Pełne rozwiązanie

Jesteśmy już gotowi do analizy przypadku dowolnego \(k\). Ponieważ każdy z \(k\) agentów musi odwiedzić spójny podgraf wierzchołków, więc dokładnie \(k - 1\) krawędzi nie będzie odwiedzonych przez żadnego agenta i całe drzewo rozpadnie się na \(k\) spójnych składowych. Znowu w każdej składowej rozwiążemy przypadek dla \(k = 1\), a odpowiedź to będzie \(2( n - k) - \sum_i \ell_i\). Tak więc aby zminimalizować wynik, należy znaleźć taki podział na spójne składowe, który zmaksymalizuje sumę odległości do najdalszych wierzchołków.

Jak jednak wyznaczyć te optymalne spójne składowe? Nie możemy przecież przeglądać wszystkich podzbiorów krawędzi do usunięcia, będzie ich bowiem wykładniczo wiele. Spróbujmy jednak nieco inaczej spojrzeć na rozwiązanie, które mamy. Zapomnijmy o podziale na spójne składowe, ale zostawmy wygenerowane przez nie ścieżki do najdalszych wierzchołków. Mamy zatem w drzewie \(k\) ścieżek: każda z nich zaczyna się w wierzchołku zawierającym agenta oraz nie przecinają się one w żadnym wierzchołku.

Ten konkretny zbiór ścieżek nie był zupełnie przypadkowy, ponieważ powstał on w wyniku zastosowania algorytmu na pewnym podziale na spójne składowe. Ale okazuje się, że jeżeli weźmiemy sobie dowolny inny zbiór rozłącznych ścieżek zaczynających się w wierzchołkach z agentami, to dla tego zbioru ścieżek będziemy mogli tak dobrać trasy agentów, żeby odwiedzały wszystkie wierzchołki oraz każda z nich zaczynała się w początku i kończyła w końcu pewnej ścieżki. Najłatwiej jest to zrobić dzieląc najpierw drzewo na spójne składowe w ten sposób, żeby w każdej składowej znajdowała się dokładnie jedna ścieżka, a następnie w każdej składowej wyznaczyć trasę agenta tak, żeby kończyła się w końcu ścieżki.

Skoro więc zależy nam na maksymalizacji sumy długości ścieżek powstałych z pewnego podziału na spójne składowe, a każdy zbiór rozłącznych ścieżek generuje nam pewien podział na spójne składowe, to nasze zadanie sprowadza się do znalezienia rozłącznego zbioru ścieżek zaczynających się w wierzchołkach z agentami o największej sumarycznej długości.

Znajdowanie rozłącznego zbioru ścieżek

Do znalezienia tego zbioru ścieżek użyjemy metody programowania dynamicznego na drzewie. Standardowo dla każdego wierzchołka \(v\) w drzewie będziemy obliczać pewne wartości na podstawie wartości obliczonych uprzednio w jego synach \(u_1,u_2,\ldots,u_s\).

Będziemy obliczać trzy różne wartości, w zależności od tego, czy krawędź z wierzchołka \(v\) do jego ojca przynależy do jakiejś ścieżki. Mamy trzy możliwości, bo krawędź ta może:

• należeć do ścieżki, której początek (czyli wierzchołek z agentem) znajduje się w poddrzewie \(v\) i ścieżka ta biegnie krawędzią w górę,

• należeć do ścieżki, której początek znajduje się poza poddrzewem i ścieżka biegnie krawędzią w dół, a jej koniec znajduje się w poddrzewie,

• w ogóle nie należeć do żadnej ścieżki.

Dla każdej z tych trzech możliwości będziemy wyznaczać maksymalną sumaryczną długość ścieżek zawartych w poddrzewie \(v\), przy czym dla ścieżki, która przechodzi przez krawędź do ojca \(v\), będziemy liczyli tylko jej część znajdującą się w poddrzewie. Wartości te oznaczymy przez \(dp_{\uparrow}[v]\), \(dp_{\downarrow}[v]\) i \(dp[v]\). Wzory będą zależały od tego, czy w wierzchołku \(v\) jest agent, czy też nie.

Załóżmy na początku, że w wierzchołku \(v\) znajduje się agent. Jeśli krawędzią do ojca ma przechodzić jakaś ścieżka, to musi ona zaczynać się w wierzchołku \(v\) i iść w górę. Wobec tego krawędzie prowadzące do synów \(v\) nie mogą należeć do żadnej ścieżki, więc w każdym poddrzewie \(u_i\) ścieżki możemy wybrać niezależnie, a ich maksymalna długość w takim poddrzewie to będzie \(dp[u]\).

Tak więc \(dp_{\uparrow}[v] = D\), gdzie \(D = \sum_i dp[u_i]\).

Natomiast niemożliwe jest, żeby ścieżka po krawędzi do ojca biegła w dół. Wobec tego przyjmiemy, że \(dp_{\downarrow}[v] = -\infty\).

Przypadek, gdy krawędzią do ojca nie biegnie żadna ścieżka, jest trochę bardziej skomplikowany.

Pierwsza możliwość jest taka, że agent z wierzchołka \(v\) nie odwiedza żadnych dodatkowych miast, wobec tego ścieżka zaczynająca się w tym wierzchołku ma długość \(0\) i również żadna krawędź do syna wierzchołka \(v\) nie zawiera ścieżki. Tak więc znowu sumujemy po prostu \(dp[u_i]\) po wszystkich dzieciach.

Druga możliwość jest taka, że ścieżka zaczynająca się w \(v\) idzie do któregoś z poddrzew \(u_i\). Wtedy do sumy \(dp[u_j]\) po wszystkich pozostałych dzieciach musimy dodać \(dp_{\downarrow}[u_i]\) po wybranym dziecku \(u_i\) plus \(1\) za krawędź z \(v\) do tego dziecka. Wzór jest zatem następujący:

\[dp[v] = \max(D,\ \max_i (D - dp[u_i] + 1 + dp_{\downarrow}[u_i])).\]

Rozważmy teraz sytuację, kiedy w wierzchołku \(v\) nie ma agenta. Jeśli krawędzią do ojca \(v\) ma podążać ścieżka w górę (a nie może ona zaczynać się w \(v\), ponieważ nie ma tam agenta), to musi zaczynać się w jakimś poddrzewie syna \(v\), potem wychodzić z tego poddrzewa krawędzią do \(v\), a następnie iść w górę krawędzią do ojca \(v\). Tak więc we wzorze musimy zrobić maksimum po wszystkich dzieciach i w wybranym dziecku zamiast \(dp[u_i]\) do sumy wziąć \(1 + dp_{\uparrow}[u_i]\):

\[dp_{\uparrow}[v] = \max_i (D - dp[u_i] + 1 + dp_{\uparrow}[u_i]).\]

Jeśli krawędzią do ojca ma przechodzić ścieżka w dół (czyli zaczynająca się gdzieś poza poddrzewem \(v\)), to mamy dwa przypadki: może ona kończyć się w wierzchołku \(v\), albo kończyć się w jakimś poddrzewie zaczepionym w dziecku \(u_i\):

\[dp_{\downarrow}[v] = \max(D,\ \max_i (D-dp[u_i] + 1 + dp_{\downarrow}[u_i])).\]

W końcu pozostaje przypadek, kiedy krawędzią do ojca nie przechodzi żadna ścieżka. Teraz mamy trzy przypadki: albo do wierzchołka \(v\) nie dochodzi żadna ścieżka, albo kończy się tam ścieżka idąca w górę z jakiegoś poddrzewa zaczepionego w dziecku, albo przez wierzchołek \(v\) przechodzi ścieżka zaczynająca się w poddrzewie dla pewnego dziecka i kończy się ona w poddrzewie dla jakiegoś innego dziecka:

\[dp[v] = \max(D,\ \max_i (D-dp[u_i] + 1 + dp_{\uparrow}[u_i]),\ \max_{i\neq j} (D-dp[u_i]-dp[u_j] + dp_{\uparrow}[u_i] + 2 + dp_{\downarrow}[u_j]))).\]

W tym przypadku musimy obliczyć maksimum po wszystkich wyborach par różnych synów. Żeby obliczyć je efektywnie, możemy zrobić sobie dodatkowe wewnętrzne programowanie dynamiczne po synach: dla ustalonego prefiksu synów będziemy pamiętać cztery wartości: sumę \(dp\) po tych synach; sumę, jeżeli dla jednego z synów wzięliśmy \(dp_{\uparrow}\); sumę, jeżeli dla jednego z synów wzięliśmy \(dp_{\downarrow}\); sumę, jeżeli wzięliśmy już zarówno syna z \(dp_{\uparrow}\), jak i syna z \(dp_{\downarrow}\).

Szukaną sumą najdłuższych ścieżek będzie oczywiście wartość \(dp\) w korzeniu drzewa.

Jaka jest złożoność czasowa tego rozwiązania? Dla ustalonego wierzchołka \(v\) wszystkie sumy i maksima jesteśmy w stanie policzyć w złożoności liniowej od liczby synów. Wobec tego całe rozwiązanie będzie działać w czasie \(O(n)\).