Omówienie zadania Wyścig kolarski (III etap XXXI OI)

Główna obserwacja

Niech \(G\) będzie rozważanym grafem skierowanym, a \(G'\) grafem nieskierowanym otrzymanym przez zignorowanie kierunków krawędzi w \(G\). Okazuje się, że wierzchołek \(s\) jest dozwoloną startową lokalizacją wtedy i tylko wtedy, gdy w grafie \(G'\) leży on na jakimś cyklu o dodatniej liczbie krawędzi.

Dowód:

• Jeżeli w grafie \(G'\) wierzchołek \(w\) nie leży na żadnym cyklu, to oczywiście nie jest dozwoloną startową lokalizacją.
• Jeżeli w grafie \(G'\) wierzchołek \(w\) leży na jakimś cyklu, to leży on na pewnym specjalnym cyklu następującej postaci: Niech \(D\) będzie zbiorem krawędzi należących do pewnego drzewa DFS w grafie \(G\) o korzeniu w wierzchołku \(1\). Wiemy, że ono istnieje, bo z wierzchołka \(1\) da się dojść do każdego innego. Wtedy wszystkie krawędzie tego specjalnego cyklu należą do zbioru \(D\) poza jedną krawędzią \((c, d)\), która do niego nie należy. Analizując kilka przypadków można zauważyć, że da się tak wybrać ścieżkę, że jak odwrócimy na niej kierunek krawędzi, to otrzymamy skierowany cykl w grafie \(G\), na którym leży wierzchołek \(w\), a więc jest on dozwoloną startową lokalizacją. Konkretniej:
  • Jeżeli zarówno \(c\) jak i \(d\) znajdują się w poddrzewie \(w\), to wystarczy zmienić kierunek na ścieżce od \(d\) do \(w\) nieidącej przez krawędź \((c, d)\).
  • Jeżeli tylko \(d\) znajduje się w poddrzewie \(w\), to wystarczy zmienić kierunek na ścieżce od \(d\) do \(lca(c, d)\) idącej przez krawędź \((c, d)\).
  • Jeżeli tylko \(c\) znajduje się w poddrzewie \(w\), to wystarczy zmienić kierunek na ścieżce od \(d\) do \(lca(c, d)\) nieidącej przez krawędź \((c, d)\).

W związku z tym całe zadanie redukuje się do grafu nieskierowanego.

Przypadek \(q = 0\)

Użyjmy więc powyższej obserwacji. Dla każdego wierzchołka wyznaczmy czy leży na jakimś nieskierowanym cyklu (o dodatniej liczbie krawędzi). Możemy to zrobić najpierw znajdując w naszym grafie drzewo DFS - drzewo powstałe po wybraniu krawędzi, przez które przechodzi wywołanie DFS. Wtedy dla każdej krawędzi \((a_i, b_i)\), która nie należy do niego, chcemy zaznaczyć każdy wierzchołek na ścieżce między \(a_i\) oraz \(b_i\). Jeżeli każdą taką krawędź obsłużymy w czasie \(O(n)\), to dostaniemy rozwiązanie w czasie \(O(nm)\), co rozwiązuje 2. podzadanie.

By rozwiązać 3. podzadanie, spróbujmy obsłużyć wszystkie te ścieżki w sumarycznej złożoności \(O(n)\). Gdyby nasze drzewo DFS było ścieżką, to można by ten problem rozwiązać tablicą różnic - w tablicy \(diff\) zwiększamy \(diff[a_i]\) o \(1\) i zmniejszamy \(diff[b_i - 1]\) o \(1\), a następnie obliczamy na niej sumy prefiksowe (zakładając, że głębokość \(a_i\) jest nie większa, niż głębokość \(b_i\)). Jeżeli uzyskana wartość jest dodatnia dla danego wierzchołka, to leży on na jakiś nieskierowanym cyklu (o dodatniej liczbie krawędzi).

Zauważmy, że w przypadku ogólnego drzewa DFS możemy postąpić tak samo. Każda krawędź niebędąca w drzewie DFS łączy wierzchołek z jakimś jego przodkiem w drzewie DFS. Dlatego będziemy wyliczać te sumy prefiksowe na tylko ścieżkach idących od korzenia.

Przypadek \(q > 0\)

Zastanówmy się, co się dzieje, gdy dochodzi nam do grafu nowa krawędź \(x_i, y_i\). Nie będzie ona należeć do naszego drzewa DFS, a więc chcielibyśmy dowiedzieć się ile jest jeszcze niezaznaczonych wierzchołków na ścieżce między \(x_i\) oraz \(y_i\). To będą dokładnie te wierzchołki, które zostaną dozwolonymi startowymi lokacjami. Aby efektywnie odpowiadać na te zapytania, możemy użyć sum prefiksowych do policzenia w tablicy \(pref\) dla każdego wierzchołka ile jest jeszcze niezaznaczonych wierzchołków na ścieżce od niego do korzenia. Wtedy odpowiedzią będzie \(pref[x_i] + pref[y_i] - 2pref[parent\_lca(x_i, y_i)]\), gdzie \(parent\_lca(x_i, y_i)\), to ojciec najniższego wspólnego przodka wierzchołków \(x_i\) oraz \(y_i\). Zostało więc tylko wyznaczenie najniższego wspólnego przodka dla każdego zapytania. Jest to standardowy problem, który można rozwiązać swoją preferowaną techniką: algorytmem Tarjana, jump pointer-y, Heavy-Light Decomposition lub Range Minimum Query.