Omówienie zadania Kolacje (II etap XXVI OI)

Dane jest drzewo o \(n\) wierzchołkach, każdy wierzchołek jest jednego z \(r\) kolorów, a krawędzie drzewa mają wagi. Niech \(dist(u,v)\) oznacza wagę ścieżki z wierzchołka \(u\) do wierzchołka \(v\).

Mamy odpowiedzieć na \(q\) zapytań postaci \(u_1,u_2,s\): jaka jest minimalna wartość \(dist(u_1,v) + dist(u_2,v)\), gdzie \(v\) jest dowolnym wierzchołkiem koloru \(s\).

Podzadania 1 i 2

Najprostsze rozwiązanie to niezależne rozpatrzenie każdego zapytania \(u_1,u_2,s\). Algorytmem DFS na drzewie możemy wyznaczyć tabelkę \(d_1[v] =\) najkrótsza odległość z wierzchołka \(u_1\) do \(v\). Analogicznie wyznaczamy \(d_2[v] =\) najkrótsza odległość z wierzchołka \(u_2\) do \(v\). W końcu bierzemy minimum z \(d_1[v] + d_2[v]\) po wszystkich wierzchołkach \(v\) koloru \(s\). Czas działania dla pojedynczego zapytania to \(O(n)\), czyli sumarycznie \(O(qn)\).

Podzadanie 4

Wszystkie wierzchołki mają ten sam kolor, zatem szukamy dowolnego wierzchołka \(v\), który minimalizuje \(dist(u_1,v) + dist(u_2,v)\). Nietrudno się przekonać, że dobrym wyborem dla wierzchołka \(v\) będzie dowolny wierzchołek, który leży na ścieżce z \(u_1\) do \(u_2\), a odpowiedzią będzie \(dist(u_1,u_2)\).

Aby szybko znajdować odległość między dowolnymi wierzchołkami w drzewie, można skorzystać z algorytmu LCA. Ukorzeńmy drzewo w pewnym wierzchołku i niech \(lev[v]\) będzie odległością wierzchołka \(v\) od korzenia. W ukorzenionym drzewie \(LCA(u_1,u_2)\) oznacza najgłębszego wspólnego przodka wierzchołków \(u_1\) i \(u_2\) (czyli wierzchołek leżący na obu ścieżkach z \(u_1\) do korzenia i z \(u_2\) do korzenia, o największej odległości od korzenia). Wtedy odległość między \(u_1\) i \(u_2\) wyraża się wzorem \[dist(u_1,u_2) = lev[u_1] + lev[u_2] - 2 \cdot lev[LCA(u_1,u_2)].\]

Obliczanie LCA jest znanym problemem i m.in. istnieją rozwiązania o koszcie preprocessingu \(O(n\log n)\) i koszcie zapytania \(O(\log n)\). Jeśli skorzystamy z takiego algorytmu, rozwiążemy podzadanie 4 w czasie \(O((n+q)\log n)\).

Podzadanie 5

Jeśli jest tylko jeden wierzchołek koloru \(s\) (oznaczmy go przez \(v\)), to odpowiedzią będzie po prostu \(dist(u_1,v) + dist(u_2,v)\). Odległości te wyznaczamy tak samo, jak w podzadaniu 4.

Podzadanie 6

Rozważmy pewien wierzchołek \(v\) koloru \(s\) i niech \(v'\) będzie wierzchołkiem na ścieżce z \(u_1\) do \(u_2\), który leży najbliżej wierzchołka \(v\). Wtedy \[dist(u_1,v) + dist(u_2,v) = dist(u_1,u_2) + 2\cdot dist(v,v').\]

Niech \(d[u] =\) minimalna odległość od wierzchołka \(u\) do dowolnego wierzchołka koloru \(s\). Taką tabelkę możemy wyznaczyć algorytmem Dijkstry, inicjując kolejkę priorytetową wszystkimi wierzchołkami koloru \(s\) (dla nich będziemy mieli \(d[u]=0\)).

Teraz w powyższym wzorze możemy zastąpić \(dist(v,v')\) przez minimalną wartość \(d[u]\) dla wierzchołków \(u\) leżących na ścieżce pomiędzy \(u_1\) i \(u_2\). Obliczanie minimum ze ścieżek w drzewie również jest standardowym problemem, dla którego mamy rozwiązanie o koszcie zapytań \(O(\log n)\).

Tak więc złożoność rozwiązania to \(O(rn\log n)\) dla preprocessingu i \(O(q\log n)\) dla zapytań.

Pełne rozwiązanie

Dla ustalonego koloru \(s\) rozważmy zbiór \(V_s\) wszystkich wierzchołków koloru \(s\) oraz wierzchołków \(u_1,u_2\) z zapytań o kolor \(s\). Zauważmy, że suma rozmiarów zbiorów \(V_s\) po wszystkich kolorach jest nie większa niż \(n+2q\) (wszystkie wierzchołki drzewa i wszystkie wierzchołki z zapytań).

Rozważmy teraz skompresowane poddrzewo indukowane wierzchołkami zbioru \(V_s\), tzn. drzewo \(T_s\), w którym zostawiamy jedynie wierzchołki i krawędzie leżące na ścieżkach między wierzchołkami z \(V_s\), oraz w którym usuwamy wszystkie wierzchołki spoza \(V_s\) o stopniu 2 (scalając krawędzie wchodzące do takiego wierzchołka).

Zauważmy, że drzewo \(T_s\) ma co najwyżej \(2|V_s|\) wierzchołków i zawiera wszystkie informacje umożliwiające obliczenie odpowiedzi na zapytania o kolor \(s\). Mając takie drzewo, robimy preprocessing jak w podzadaniu 6 w czasie \(O(|V_s|\log n)\) i odpowiadamy na każde zapytanie w czasie \(O(\log n)\).

Zatem sumaryczny preprocessing wszystkich drzew to czas \(O((n+q)\log n)\), a zapytania to czas \(O(q\log n)\).

Konstrukcja skompresowanego drzewa

Ukorzeńmy drzewo w dowolnym wierzchołku. Okazuje się, że jeśli będziemy przeglądać wierzchołki zbioru \(V_s\) w kolejności wchodzenia do nich algorytmem DFS (niech to będzie kolejność \(v_1,v_2,\ldots,v_{|V_s|}\)), to do skompresowanego drzewa (poza wierzchołkami z \(V_s\)) będą należeć wierzchołki \(LCA(v_i,v_{i+1})\) dla \(1\leq i< |V_s|\).

Teraz gdy mamy wierzchołki z \(T_s\) posortowane w kolejności DFS (niech to będzie kolejność \(w_1,w_2,\ldots\)), to krawędziami z \(T_s\) są ścieżki z \(LCA(w_i,w_{i+1})\) do \(w_{i+1}\) w oryginalnym drzewie.

Zatem mając algorytm na wyznaczanie LCA, konstrukcję drzewa \(T_s\) możemy zrobić w czasie \(O(|V_s|\log n)\), czyli wszystkie drzewa zbudujemy w czasie \(O(n\log n)\).