Omówienie zadania Dwukolorowe drzewo (II etap XXXIII OI)

Rozwiązanie \(O(n^2\cdot 2^n)\) - podzadanie \(n\leq 16\)

Za pomocą masek bitowych lub rekurencji możemy przeiterować się po wszystkich możliwych kolorowaniach węzłów drzewa. Dla każdego z nich sprawdzamy, czy liczby czarnych i białych węzłów są równe, i pozostawiamy tylko te kolorowania, dla których jest to prawdą.

Wygenerowawszy poprawne kolorowania, możemy dla każdego z nich obliczyć sumę odległości między parami węzłów o tych samych kolorach w złożoności \(O(n^2)\). W tym celu z każdego węzła drzewa uruchamiamy algorytm przeszukiwania w głąb, który znajduje odległości do wszystkich pozostałych węzłów. Następnie sumujemy odległości do węzłów o tym samym kolorze, co węzeł źródłowy. Złożoność tego kroku dla jednego źródła to \(O(n)\), a więc, uruchamiając ten algorytm ze wszystkich węzłów drzewa po kolei, otrzymujemy złożoność \(O(n^2)\).

Powyższe rozwiązania daje nam więc całkowitą złożoność \(O(2^n\cdot n^2)\). Uważny Czytelnik może zwrócić uwagę na fakt, że sumę odległości obliczamy nie dla każdego kolorowania, ale tylko dla tych, w których mamy równą liczbę białych i czarnych węzłów. Takich węzłów jest dokładnie \(n \choose n/2\), co asymptotycznie jest równe \(O(\frac{2^n}{\sqrt{n}})\) (aby to udowodnić, można np. skorzystać ze wzoru Stirlinga). W związku z tym możemy podać lepszą asymptotyczną złożoność tego rozwiązania, czyli \(O(2^n\cdot n^{3/2})\).

Rozwiązanie \(O(n\cdot 2^n)\) - podzadanie \(n\leq 24\)

Skorzystajmy z pomysłu podobnego do poprzedniego podzadania, jednak tym razem spróbujemy obliczyć sumę odległości dla ustalonego kolorowania w \(O(n)\) zamiast \(O(n^2)\).

Załóżmy więc, że kolorowanie jest ustalone. Rozważmy pewną dowolnie wybraną krawędź w drzewie i zastanówmy się, ile ścieżek między węzłami tych samych kolorów przechodzi przez tę krawędź. Nasza krawędź dzieli drzewo na dwie części - wszystko co znajduje się po jej jednej stronie oraz wszystko, co znajduje się po jej drugiej stronie. Jeśli po jednej ze stron mamy \(c\) węzłów czarnych oraz \(b\) węzłów białych, to po drugiej stronie będziemy mieli \(n/2-c\) węzłów czarnych oraz \(n/2-b\) węzłów białych. W związku z tym poszukiwana liczba ścieżek wyniesie \[ c\cdot (n/2-c) + b\cdot (n/2-b). \] Jeśli zsumujemy te wartości dla każdej krawędzi drzewa, otrzymamy łączną sumę długości wszystkich ścieżek między parami węzłów o tych samych kolorach.

Pozostało nam więc pokazać, jak obliczyć wartości \(c\) oraz \(b\) dla każdej krawędzi drzewa. W tym celu możemy ukorzenić drzewo w dowolnym węźle i skorzystać z programowania dynamicznego. Niech \(\text{dzieci}(v)\) oznacza zbiór dzieci węzła \(v\) w ukorzenionym drzewie. Wówczas mamy wzory \[ c[v] = \left(\sum_{u\in \text{dzieci}(v)}c[u]\right) + \begin{cases} 1\qquad\text{ jeśli }v\text{ jest czarny}\\0\qquad\text{ w przeciwnym przypadku}\end{cases} \] oraz \[ b[v] = \left(\sum_{u\in \text{dzieci}(v)}b[u]\right) + \begin{cases} 1\qquad\text{ jeśli }v\text{ jest biały}\\0\qquad\text{ w przeciwnym przypadku}\end{cases} \] które pozwalają nam obliczyć wartości \(c\) oraz \(b\) dla wszystkich węzłów drzewa w łącznym czasie \(O(n)\).

Pozostało zauważyć, że dla każdego węzła \(v\), który nie jest wybranym korzeniem drzewa, wyznaczone wartości \(c[v]\) oraz \(b[v]\) odpowiadają liczbie węzłów czarnych i białych po jednej stronie krawędzi łączącej \(v\) z jego rodzicem. W związku z tym wynik to suma po \(c[v]\cdot (n/2-c[v]) + b[v]\cdot (n/2-b[v])\) dla wszystkich węzłów \(v\) poza korzeniem.

Naiwne szacowanie złożoności czasowej tego rozwiązanie to \(O(2^n\cdot n)\). Ponadto, ponownie jak w poprzednim rozwiązaniu, jeśli będziemy bardziej dokładni, możemy podać lepszą asymptotyczną złożoność, czyli \(O(2^n\cdot n^{1/2})\).

Rozwiązanie \(O(n^2)\) - podzadanie \(n\leq 5000\)

W tym rozwiązaniu wprowadzimy pomysł oparty o programowanie dynamiczne. Ukorzeńmy drzewo w dowolnym węźle. Następnie dla węzła \(v\) oraz liczby \(c\) będącej w zakresie od 0 do liczby węzłów w poddrzewie \(v\) (włącznie) definiujemy \(\text{dp}[v][c]\) jako maksymalną sumę po wszystkich krawędziach w poddrzewie \(v\) wartości \(c\cdot (n/2-c) + b\cdot (n/2-b)\), gdzie \(b\) to liczba węzłów białych w poddrzewie pod daną krawędzią, a \(c\) to liczba węzłów czarnych w tym poddrzewie, zakładając, że w poddrzewie \(v\) jest dokładnie \(c\) węzłów czarnych. Wówczas odpowiedzią na nasze zadanie będzie \(\text{dp}[r][n/2]\), gdzie \(r\) to korzeń drzewa.

Zastanówmy się jak obliczać wartości \(dp\). Jeśli \(v\) jest liściem, to \(\text{dp}[v][0]=0\) oraz \(\text{dp}[v][1]=0\). Załóżmy więc, że \(v\) nie jest liściem i ma dzieci \(u_1,u_2,\ldots,u_k\). Przez \(s[u]\) oznaczymy rozmiar poddrzewa o korzeniu w \(u\). Wówczas, aby obliczyć \(\text{dp}[v][c]\), musimy rozważyć wszystkie możliwe rozkłady liczby \(c\) wśród dzieci \(v\) oraz wziąć pod uwagę, że sam \(v\) także może być czarny. Otrzymujemy więc wzór \[ \text{dp}[v][c] = \max_{c_1+c_2+\ldots+c_k\in \{c-1,c\}} \left(\sum_{i=1}^k \text{dp}[u_i][c_i] + c_i\cdot (n/2-c_i) + (s[u_i]-c_i)\cdot (n/2-(s[u_i]-c_i))\right), \] przy czym w maksimum uwzględniamy tylko takie \(c_i\), które są nieujemne i nie większe niż \(s[u_i]\). Zwróćmy uwagę, że wartości \(c_i\) mogą sumować się do \(c\) lub \(c-1\), ponieważ \(v\) może być czarny lub biały.

Zwróćmy uwagę, że ten problem bardzo przypomina znany problem plecakowy, w którym chcemy zapakować plecak rozmiaru dokładnie \(c\) lub \(c-1\) przedmiotami tak, aby zmaksymalizować ich całkowitą wartość (sumę długości ścieżek).

Przy uważnej implementacji, której szczegóły pozostawimy Czytelnikowi, możemy obliczyć wszystkie wartości \(\text{dp}\) w czasie \(O(n^2)\).

Rozwiązanie \(O(n)\) - wzorcowe

Ukorzeńmy drzewo w dowolnym węźle. Następnie rozważmy dowolny węzeł \(v\), który nie jest korzeniem. Podobnie jak w rozwiązaniu \(O(2^n\cdot n)\), zastanowimy się, ile ścieżek między węzłami tych samych kolorów przechodzi przez krawędź łączącą \(v\) z jego rodzicem. Jeśli w poddrzewie \(v\) mamy \(c\) węzłów czarnych oraz \(b\) węzłów białych, to liczba tych ścieżek wyniesie \[ c\cdot (n/2-c) + b\cdot (n/2-b). \]

Zastanówmy się, jakie wartości \(c\) oraz \(b\) maksymalizują nasze wyrażenie. Przez \(s=c+b\) oznaczmy łączną liczbę węzłów w poddrzewie \(v\). Wówczas nasze wyrażenie możemy przekształcić do postaci \[ \begin{align*} c\cdot (n/2-c) + (s-c)\cdot (n/2-(s-c)) &= cn/2 - c^2 + sn/2 - s^2 + cs - cn/2 + cs - c^2 \\ &= -2c^2 + 2cs + sn/2 - s^2\\ &= 2c(s-c) + \text{const}, \end{align*} \] gdzie \(\text{const}\) to część, która nie zależy od \(c\), tylko od \(n\) oraz rozważanego węzła \(v\). Nietrudno przekonać się, że wyrażenie \(c(s-c)\) osiąga maksymalną wartość dla \(c=s/2\).

Otrzymaliśmy więc, że jeśli \(s\) jest parzyste, to liczba ścieżek między węzłami o tych samych kolorach przechodzących przez krawędź łączącą \(v\) z jego rodzicem jest maksymalna, gdy w poddrzewie \(v\) jest tyle samo węzłów czarnych i białych.

Zastanówmy się, co się dzieje, gdy \(s\) jest nieparzyste. Przyjrzymy się dokładniej wyrażeniu \(c(s-c)\). Jest to funkcja kwadratowa, która rośnie wraz ze wzrostem \(c\) dla \(c\lt s/2\) oraz maleje dla \(c \gt s/2\). W takim razie, jeśli poszukujemy całkowitego \(c\), które maksymalizuje \(c(s-c)\), to wystarczy rozważyć wartości \(c\) najbliższe do \(s/2\), czyli \(c=\lfloor s/2\rfloor=(s-1)/2\) oraz \(c=\lceil s/2\rceil=(s+1)/2\). Nietrudno obliczyć, że dla obu tych wartości \(c\) wartośc wyrażenia \(c(s-c)\) jest taka sama i wynosi \((s^2-1)/4\). Oznacza to, że w przypadku, gdy \(s\) jest nieparzyste, liczba ścieżek między węzłami o tych samych kolorach przechodzących przez krawędź łączącą \(v\) z jego rodzicem jest maksymalna, gdy w poddrzewie \(v\) liczby węzłów czarnych i białych różnią się o co najwyżej jeden.

Przedstawimy więc konstrukcję kolorowania, dla którego w poddrzewach o rozmiarze parzystym liczby węzłów czarnych i białych są równe, a dla poddrzew o rozmiarze nieparzystym liczby węzłów czarnych i białych różnią się o jeden. Wówczas dla każdej krawędzi w drzewie osiągniemy maksymalną możliwą liczbę ścieżek między węzłami o tych samych kolorach przechodzących przez tę krawędź. W związku z tym suma długości wszystkich takich ścieżek będzie maksymalna możliwa.

Nasz algorytm kolorowania będzie rekurencyjny. Zdefiniujmy procedurę, która bierze węzeł \(v\) i koloruje jego poddrzewo w taki sposób, że

jeśli rozmiar poddrzewa \(v\) jest parzysty, to liczby węzłów czarnych i białych w tym poddrzewie są równe,
jeśli rozmiar poddrzewa \(v\) jest nieparzysty, to liczba węzłów białych jest dokładnie o jeden większa od liczby węzłów czarnych,
poddrzewo każdego węzła \(u\) znajdującego się w poddrzewie \(v\) zawiera liczby węzłów czarnych i białych różniące się o co najwyżej jeden.

Innymi słowy, procedura ta produkuje pożądane przez nas kolorowanie poddrzewa \(v\) oraz zapewnia, że jeśli poddrzewo \(v\) ma rozmiar nieparzysty, to węzłów białych jest o jeden więcej niż węzłów czarnych.

Opiszmy działanie tej procedury. Jeśli \(v\) jest liściem, to wystarczy pokolorować go na biało i wówczas podane warunki są spełnione. Załóżmy więc, że \(v\) liściem nie jest, czyli posiada dzieci. Wywołujemy tę procedurę rekurencyjnie dla każdego dziecka węzła \(v\). W wyniku tych wywołań otrzymujemy kolorowania poddrzew dzieci \(v\), które spełniają warunki opisane powyżej. Pokażmy jak na ich podstawie otrzymać kolorowanie poddrzewa \(v\), które również spełnia te warunki. Dzieci mogą mieć parzyste oraz nieparzyste rozmiary swoich poddrzew. Załóżmy, że \(v\) ma \(k\) dzieci o nieparzystym rozmiarze poddrzew. Rozważamy dwa przypadki:

jeśli \(k\) jest parzyste, to wiemy, że suma rozmiarów poddrzew dzieci \(v\) jest parzysta, więc rozmiar poddrzewa \(v\) jest nieparzysty (bo dochodzi jeszcze jeden węzeł - sam \(v\)). Wówczas możemy pokolorować \(v\) na biało, a następnie dla dokładnie połowy z \(k\) dzieci o nieparzystym rozmiarze poddrzew przemalowujemy ich poddrzewo tak, że każdy węzeł czarny staje się białym, a każdy węzeł biały staje się czarnym. Wówczas w \(k/2\) poddrzewach dzieci \(v\) mamy nadwyżkę (o jeden) białych węzłów, a w innych \(k/2\) poddrzewach dzieci \(v\) mamy nadwyżkę (znów o jeden) czarnych węzłów, które to nadwyżki wzajemnie się znoszą. Ostatecznie w poddrzewie \(v\) mamy o jeden więcej białych węzłów niż czarnych, ponieważ \(v\) jest biały, a w poddrzewach dzieci \(v\) łączna liczba białych i czarnych jest równa.
jeśli \(k\) jest nieparzyste, to wiemy, że suma rozmiarów poddrzew dzieci \(v\) jest nieparzysta, więc rozmiar poddrzewa \(v\) jest parzysty. Wówczas możemy pokolorować \(v\) na biało, a następnie dla dokładnie \((k+1)/2\) dzieci o nieparzystym rozmiarze poddrzew przemalowujemy ich poddrzewo tak, że każdy węzeł czarny staje się białym, a każdy węzeł biały staje się czarnym. Wówczas w \((k+1)/2\) poddrzewach dzieci \(v\) mamy nadwyżkę (o jeden) czarnych węzłów, a w innych \((k-1)/2\) poddrzewach dzieci \(v\) mamy nadwyżkę (o jeden) białych węzłów, co łącznie daje o jeden czarny węzeł więcej w poddrzewach dzieci \(v\). Jeśli więc pomalujemy \(v\) na biało, to w poddrzewie \(v\) liczby białych i czarnych węzłów będą równe.

Jest jasne, że w wyniku tej procedury otrzymujemy kolorowanie poddrzewa \(v\), które spełnia pierwsze dwa z opisanych wyżej warunków. Trzeci warunek również jest spełniony, ponieważ w poddrzewie \(v\) mamy co najwyżej o jeden więcej białych węzłów niż czarnych, a wszystkie poddrzewa dzieci \(v\) spełniają ten warunek z założenia, że procedura zadziałała dla nich poprawnie (przy czym należy zwrócić uwagę, że operacja przemalowania całego poddrzewa dziecka \(v\) nie psuje trzeciego warunku).

Korzystając z tej procedury, możemy pokolorować całe drzewo, wywołując ją dla jego korzenia. Otrzymane kolorowanie osiąga maksymalną sumę długości ścieżek między węzłami o tych samych kolorach, jednak naiwna implementacja opisanej tu procedury prowadzi do złożoności czasowej \(O(n^2)\), ponieważ każdy węzeł może być przemalowany \(O(n)\) razy.

Aby uzyskać złożoność \(O(n)\), możemy wykonywać przemalowania w sposób leniwy. Jeśli chcemy przemalować całe poddrzewo dziecka \(u\) węzła \(v\), to zamiast iterować się po wszystkich węzłach poddrzewa \(u\), możemy na krawędzi prowadzącej z \(v\) do \(u\) umieścić informację o tym, że wszystko, co znajduje się pod tą krawędzią, ma zostać przemalowane. Wówczas dla każdej krawędzi mamy informację o tym, czy węzły węzły znajdujące się pod tą krawędzia mają być przemalowane, czy nie.

Wyprodukowawszy takie informacje, możemy wykonać kolejne przeszukanie drzewa, idąc od korzenia do liści. Podczas tego przejścia, możemy pamiętać, ile razy minęliśmy krawędź, która nakazuje przemalowanie na ścieżce od korzenia do aktualnie rozpatrywanego węzła. Jeśli ta liczba jest nieparzysta, to kolor węzła należy zamienić na przeciwny, a w przeciwnym przypadku nie trzeba nic robić.

Powyższa konstrukcja jest zarazem rozwiązaniem zadania, jak i dowodem, że istnieje kolorowanie osiągające wskazaną wcześniej maksymalną sumę długości ścieżek między węzłami o tych samych kolorach.

W ten sposób otrzymujemy ostateczne rozwiązanie, które działa w złożonosci czasowej \(O(n)\).