Omówienie zadania Park linowy (III etap XXX OI)

Oznaczmy przez \( w_i \) wysokość, na której chcemy zawiesić podest na drzewie \( i \).

Zauważmy, że graf, który otrzymujemy w zadaniu, jest drzewem. W drzewie tym wyróżniamy dwa rodzaje krawędzi:

• nieskierowane: \( a_i \leftrightarrow b_i \) (dla \( d_i = 0 \)), platformy \( a_i \) i \( b_i \) muszą znajdować się na różnych wysokościach, czyli \( w_{a_i} \neq w_{b_i} \).
• skierowane: \( a_i \overset{n}{\longrightarrow} b_i \) oraz \( b_i \overset{w}{\longleftarrow} a_i \) (dla \( d_i = 1 \)), mówi nam, że platforma na drzewie \( a_i \) musi być niżej niż ta na drzewie \( b_i \), czyli \( w_{a_i} < w_{b_i} \).

Podzadanie \( n \leq 1500 \)

Będziemy operować na ukorzenionym drzewie.

Dla każdej pary \( (x, w_x) \) - wierzchołka w drzewie i wartości \( w_x \), którą chcemy w nim ustalić, policzymy wartość \( DP(x)(w_x+) \).

Będzie to najmniejsza liczba naturalna \( d \), taka że w poddrzewie \( x \) we wszystkich wierzchołkach \( w_i \) będzie nie większe niż \( d \). Naszą odpowiedzią będzie wtedy \( \min(DP(x)(i) | i \in \{0, \ldots, n - 1\}) \), dla \( x \) będącego korzeniem.

Algorytmem DFS przejdziemy po drzewie i w każdym wierzchołku \( x \) będziemy liczyć wartości \( DP(x)(y) \) w następujący sposób:

• Jeśli \( x \) jest liściem to dla każdego \( y \), \( DP(x)(y) = y \).
• W przeciwnym razie najpierw zejdziemy DFSem do synów \( x \) i w nich policzymy wartości \( DP \), a następnie na ich podstawie policzymy \( DP \) dla \( x \).

Zastanówmy się teraz, jak obliczyć \( DP(x)(y) \) dla konkretnych \( x \) i \( y \) w drugim przypadku.

We wszystkich synach \( s_i \) wierzchołka \( x \) chcemy ustalić taką wysokość \( w_{s_i} \), że nie powoduje ona konfliktu z krawędzią pomiędzy \( x \) i \( s_i \) oraz \( DP(s_i)(w_{s_i}) \) jest jak najmniejsze.

W takim razie musi zachodzić:

• \( DP(x)(y) \geq \min(DP(s_i)(z) | z \neq y) \) dla \( x \leftrightarrow s_i \), bo \( w_x \neq w_{s_i} \).
• \( DP(x)(y) \geq \min(DP(s_i)(z) | z > y) \) dla \( x \overset{n}{\longrightarrow} s_i \), bo \( w_x < w_{s_i} \).
• \( DP(x)(y) \geq \min(DP(s_i)(z) | z < y) \) dla \( x \overset{w}{\longleftarrow} s_i \), bo \( w_x > w_{s_i} \).
• \( DP(x)(y) \geq y \).

Aby efektywnie obliczyć \( DP \) musimy w każdym wierzchołku policzyć minimalne \( DP(x) \) na prefixie i sufiksie. To pozwoli nam na sprawdzanie wartości \( \min(DP(s_i)(z) | \ldots) \) w \( O(1) \).

Całkowitą złożonością tego rozwiązania jest więc \( O(n^2) \), ponieważ dla każdej pary \( (x, y) \) musimy przejść po wszystkich krawędziach wychodzących z \( x \), a łącznie krawędzi w drzewie jest \( n - 1 \).

Podzadanie, w którym \( d_i = 1 \) dla wszystkich \( 1 \leq i < n \)

W tym przypadku mamy tylko krawędzie skierowane.

Tym razem podejdziemy do problemu z trochę innym \( DP \) oraz dołożymy wyszukiwanie binarne do wyniku.

Zauważmy, że jeśli da się tak ustalić wartości \( w_i \), że maksymalna wartość \( w_i \) to \( d \), to da się też ustalić je tak, aby to maksimum było równe \( d + m \) dla każdego \( m \in \mathbb{N}\). Widzimy więc, że możemy wyszukać binarnie najmniejsze możliwe \( d \).

Tym razem dla każdego wierzchołka \( x \) będziemy liczyć \( DP_{MIN}(x) \) i \( DP_{MAX}(x) \), czyli minimalną i maksymalną możliwą do uzyskania wartość \( w_x \) przy założeniu, że w poddrzewie \( x \) wszystkie platformy są zawieszone na wysokości co najwyżej \( d \).

Przy liczeniu \( DP \) musimy uwzględnić następujące nierówności:

• \( x \overset{n}{\longrightarrow} s_i \): \( DP_{MIN}(x) < DP_{MAX}(s_i) \) i \( DP_{MAX}(x) < DP_{MAX}(s_i) \)
• \( x \overset{w}{\longleftarrow} s_i \): \( DP_{MIN}(x) > DP_{MIN}(s_i) \) i \( DP_{MAX}(x) > DP_{MIN}(s_i) \)
• \( DP_{MIN}(x) \leq DP_{MAX}(x) \leq d \)

Jeśli dla jakiegoś \( x \) nie da się zaspokoić tych nierówności, to \( d \) jest oczywiście zbyt małe. W przeciwnym razie możemy sprawdzać mniejsze \( d \).

To rozwiązanie działa oczywiście w złożoności \( O(n \log n) \), ponieważ jednorazowe policzenie \( DP \) to koszt \( O(n) \), a wykonujemy je \( \log n \) razy ze względu na wyszukiwanie binarne.

Podzadanie \( n \leq 200\,000 \)

Okazuje się, że do poprzedniego podzadania niewiele trzeba dodać, aby dostać pełne rozwiązanie.

Zastanówmy się, jak na \( DP_{MIN}(x) \) i \( DP_{MAX}(x) \) wpłynie syn \( s_i \) połączony z \( x \) krawędzią nieskierowaną.

Zauważmy, że sprawia on problem tylko wtedy, gdy \( DP_{MIN}(s_i) = DP_{MAX}(s_i) \). Dla \( DP_{MIN}(s_i) < DP_{MAX}(s_i) \), \( w_{s_i} \) może przybrać 2 różne wartości, więc dla każdego potencjalnego \( w_x \) wybieramy na \( w_{s_i} \) wartość różną od \( w_x \).

W takim razie musimy rozważyć przypadek istnienia synów \( x: s_1, s_2, \ldots, s_k \) takich, że \( DP_{MIN}(s_i) = DP_{MAX}(s_i) \). Oczywiście \( w_{s_i} \) jest wtedy równe wartościom \( DP \).

Tacy synowie sprawiają, że policzony tak jak w drugim podzadaniu przedział \( [DP_{MIN}(x), DP_{MAX}(x)] \) obejmuje też wartości \( y \), których nie możemy przyjąć jako \( w_x \). Spróbujmy jednak to naprawić: zwiększmy \( DP_{MIN}(x) \) na najmniejszą wartość taką, że wśród powyższych \( s_i \) nie istnieje taki, że \( w_{s_i} = DP_{MIN}(x) \). Analogicznie zmniejszmy \( DP_{MAX}(x) \).

Mogłoby się wydawać, że to nie rozwiązuje jeszcze naszego problemu - przedział wyznaczany przez \( DP \) cały czas może być "dziurawy". Okazuje się jednak, że to nam nie przeszkadza:

• Jeśli łączy nas z ojcem krawędź nieskierowana to przy obliczaniu wartości \( DP \) w ojcu wierzchołek x nie będzie brany pod uwagę, ponieważ mamy co najmniej 2 wartości do wyboru (w przeciwnym razie przedział nie jest "dziurawy").
• Jeśli jest to krawędź skierowana, to i tak zawsze optymalnie jest przypisać \( w_x \) wartość \( DP_{MIN}(x) \) lub \( DP_{MAX}(x) \) w zależności od skierowania krawędzi.

Mamy więc pełne rozwiązanie!

Aktualizacja \( DP_{MIN}(x) \) i \( DP_{MAX}(x) \) z uwzględnieniem krawędzi nieskierowanych to dla konkretnego \( x \) koszt wprost proporcjonalny do liczby synów, czyli łącznie \( O(n) \) dla wszystkich \( x \) w drzewie.

A więc pełne rozwiązanie ma złożoność czasową \( O(n \log n) \) i pamięciową \( O(n) \).