Omówienie zadania Bitada (I etap XXXII OI)

Treść zadania

W zadaniu dane są dwa nieukorzenione drzewa etykietowane \(T_1\) i \(T_2\), każde z nich o maksymalnym stopniu wierzchołka nie większym niż 3. Oznaczamy \(n=|T_1|\) oraz \(m=|T_2|\). Przez zanurzenie drzewa \(T_1\) w drzewo \(T_2\) rozumiemy takie takie przypisanie każdemu wierzchołkowi drzewa \(T_1\) wierzchołka drzewa \(T_2\), że dla każdej krawędzi \(uv\) drzewa \(T_1\) wierzchołki z \(T_2\) przypisane do \(u\) i \(v\) są połączone krawędzią w \(T_2\). Naszym celem jest obliczenie liczby zanurzeń drzewa \(T_1\) w drzewie \(T_2\), przy czym dwa zanurzenia uznajemy za różne, jeśli istnieje wierzchołek drzewa \(T_1\), który w jednym zanurzeniu jest przypisany do innego wierzchołka niż w drugim. Jako że wynik może być duży, w zadaniu mamy podać resztę z dzielenia wyniku przez zadaną liczbę \(M\).

Podzadanie \(n,m\leq 10\)

W tym podzadaniu możemy przeiterować się po wszystkich możliwych przypisaniach wierzchołków drzewa \(T_2\) do wierzchołków drzewa \(T_1\) i sprawdzić, czy spełniają one warunki zanurzenia. Aby to wykonać, możemy najprościej przeiterować się po wszystkich permutacjach liczb \(1,2,\dots,m\) i dla każdej z nich założyć, że pierwsze \(n\) elementów permutacji to przypisanie wierzchołków drzewa \(T_2\) do poszczególnych wierzchołków drzewa \(T_1\). Innymi słowy, mając permutację \(p_1,p_2,\dots,p_m\), zakładamy, że w przypisaniu wierzchołek o numerze \(i\) w drzewie \(T_1\) jest przypisany do wierzchołka o numerze \(p_i\) w drzewie \(T_2\) dla \(1\leq i\leq n\). Następnie sprawdzamy, czy dla każdej krawędzi \(uv\) drzewa \(T_1\) wierzchołki z \(T_2\) przypisane do \(u\) i \(v\) są połączone krawędzią w \(T_2\). Jeśli tak, to zwiększamy liczbę zanurzeń o 1.

Zauważmy, że w ten sposób każde zanurzenie zliczymy \((m-n)!\) razy, gdyż pozostałe \(m-n\) elementów permutacji można dowolnie ustawić dla każdego z zanurzeń. Wynik należy więc podzielić przez tę wartość (i wziąć resztę z dzielenia przez \(M\)).

Takie rozwiązanie działa w złożoności \(O(n\cdot m!)\), co jest wystarczające dla tego podzadania.

Podzadanie \(n,m\leq 30\)

Ukorzeńmy drzewo \(T_1\) w wierzchołku numer 1. Ustalmy wierzchołek \(p\) drzewa \(T_2\) i załóżmy, że korzeń \(T_1\) przechodzi na \(p\). Ukorzeńmy drzewo \(T_2\) w \(p\). Chcemy teraz zliczyć zanurzenia ukorzenionego drzewa \(T_1\) w ukorzenionym drzewie \(T_2\). Możemy skorzystać z programowania dynamicznego. Niech \(dp[u][v]\) oznacza liczbę zanurzeń poddrzewa drzewa \(T_1\) o korzeniu w wierzchołku \(u\) w poddrzewie drzewa \(T_2\) o korzeniu w wierzchołku \(v\).

Załóżmy, że chcemy obliczyć \(dp[u][v]\) i znamy wartości \(dp[w][t]\) dla wszystkich wierzchołków \(w\) i \(t\), które są dziećmi wierzchołków, odpowiednio, \(u\) i \(v\). Najpierw zauważmy, że jeśli \(u\) ma więcej dzieci w drzewie \(T_1\) niż \(v\) w drzewie \(T_2\), to nie da się zanurzyć poddrzewa o korzeniu w \(u\) w poddrzewie o korzeniu w \(v\). W takim razie \(dp[u][v]=0\). W przeciwnym przypadku musimy rozważyć wszystkie przypisania dzieci wierzchołka \(u\) do dzieci wierzchołka \(v\). Niech \(k\) będzie liczbą dzieci wierzchołka \(u\). Oznaczmy te dzieci jako \(c_1,c_2,\dots,c_k\). Założymy, że przypisujemy je kolejno do \(w_1,w_2,\dots,w_k\), gdzie \(w_i\) to zbiór parami różnych dzieci wierzchołka \(v\). Wówczas liczba zanurzeń przy tym przypisaniu wynosi \[ \prod_{i=1}^k dp[c_i][w_i]. \] Aby obliczyć wartość \(dp[u][v]\), musimy zsumować wartości dla wszystkich możliwych przypisań (i wziąć modulo \(M\)). Aby to wygodnie zaimplementować, możemy użyć funkcji rekurencyjnej, która generuje wszystkie możliwe przypisania dzieci wierzchołka \(u\) do dzieci wierzchołka \(v\).

Zauważmy, że liczba możliwych przypisań jest \(O(1)\) ze względu na ograniczenie stopni wierzchołków w drzewach. Możemy więc obliczyć wartość \(dp[u][v]\) w czasie \(O(1)\) dla dowolnych wierzchołków \(u\) i \(v\).

Aby obliczyć całą tablicę \(dp\), możemy wykonać przeszukiwanie wszerz w drzewie \(T_2\), rozpoczynając z korzenia \(p\). Będąc w wierzchołku \(v\), najpierw wywołujemy się rekurencyjnie dla wszystkich dzieci \(w\) wierzchołka \(v\) i dla każdego z nich obliczamy \(dp[u][w]\) dla wszystkich wierzchołków \(u\). Wówczas mamy wszystkie potrzebne wartości, aby obliczyć \(dp[u][v]\).

Obliczywszy wartości \(dp[u][v]\) dla wszystkich wierzchołków \(u\) i \(v\), możemy odpowiedzieć na pytanie o liczbę zanurzeń drzewa \(T_1\) ukorzenionego w 1 w drzewie \(T_2\) ukorzenionym w \(p\). Jest to po prostu wartość \(dp[1][p]\).

Widzimy, że całą tablicę \(dp\) możemy obliczyć w czasie \(O(n\cdot m)\). Proces ten musimy powtórzyć dla każdego możliwego wyboru korzenia \(T_2\), który możemy wybrać na \(m\) sposobów. Oczywiście odpowiedzią będzie suma otrzymanych wartości dla każdego możliwego wyboru korzenia. Stąd całkowita złożoność tego rozwiązania wynosi \(O(n\cdot m^2)\), co pozwalało na rozwiązanie tego podzadania.

Podzadanie \(n\leq 30\)

Zauważmy, że możemy przyspieszyć rozwiązanie opisane w punkcie wyżej. Wystarczy zauważyć, że ustaliwszy korzeń \(p\) drzewa \(T_2\), wystarczy obliczać tylko wartości \(dp[u][v]\) dla wierzchołków \(u\) i \(v\) takich, że odległość \(u\) do korzenia \(T_1\) jest równa odległości \(v\) do korzenia \(T_2\).

Jeśli przez \(l_i\) oznaczymy liczbę wierzchołków w drzewie \(T_1\) oddalonych od korzenia o \(i\), a przez \(d_i\) liczbę wierzchołków w drzewie \(T_2\) oddalonych od korzenia o \(i\), to złożoność obliczenia \(dp\) dla ustalonego korzenia \(p\) będzie liniowa względem sumy \[ \sum_{i=1}^{\min(n,m)} l_i\cdot d_i. \]

Pesymistyczna złożoność tego rozwiązania to wciąż \(O(n\cdot m^2)\), jednak z lepszą stałą. Takie usprawnienie pozwala na rozwiązanie tego podzadania.

Podzadanie \(n\leq 3\)

W tym podzadaniu możemy rozważyć przypadki w zależności od wartości \(n\). Jeśli \(n=1\), to mamy oczywiście \(m\) zanurzeń \(T_1\) w \(T_2\). Jeśli \(n=2\), to liczba zanurzeń jest równa liczbie krawędzi w \(T_2\) pomnożonej przez 2, czyli po prostu \(2\cdot (m-1)\). Wynika to stąd, że każde zanurzenie drzewa \(T_1\) w drzewo \(T_2\) musi przypisywać wierzchołki drzewa \(T_1\) do końców pewnej krawędzi drzewa \(T_2\). Takie zanurzenie można więc zrealizować na dwa sposoby, przypisując wierzchołki drzewa \(T_1\) w dwóch różnych kolejnościach. W obu tych przypadkach złożoność naszego algorytmu wynosi \(O(1)\) - nie ma nawet potrzeby wczytywania opisów drzew.

Pochylmy się nad przypadkiem, w którym \(n=3\). Wówczas zauważmy, że drzewo \(T_1\) jest ścieżką. Niech \(v\) będzie wierzchołkiem \(T_1\) pośrodku tej ścieżki. Załóżmy, że \(v\) przechodzi na wierzchołek \(u\) w \(T_2\). Wówczas dwaj sąsiedzi \(v\) w \(T_1\) muszą przechodzić na sąsiadów \(u\) w \(T_2\). Jeżeli przez \(\text{deg}_{T_2}(u)\) oznaczymy stopień wierzchołka \(u\) w drzewie \(T_2\), to mamy \(\text{deg}_{T_2}(u)\cdot (\text{deg}_{T_2}(u)-1)\) możliwości przypisań sąsiadów \(v\) w \(T_1\) do sąsiadów \(u\) w \(T_2\), gdyż dla pierwszego sąsiada mamy \(\text{deg}_{T_2}(u)\) możliwości, a dla drugiego \(\text{deg}_{T_2}(u)-1\) możliwości. Zatem liczba zanurzeń drzewa \(T_1\) w drzewie \(T_2\) wynosi \[ \sum_{u\in T_2} \text{deg}_{T_2}(u)\cdot (\text{deg}_{T_2}(u)-1). \] Taką sumę możemy obliczyć w czasie \(O(m)\), co pozwala na rozwiązanie tego podzadania.

Rozwiązanie pełne

Ukorzeńmy drzewo \(T_2\) w dowolnym wierzchołku. Niech \(v\) będzie pewnym wierzchołkiem drzewa \(T_2\). Następnie niech \(u\) i \(w\) będą wierzchołkami połączonymi krawędzią w \(T_1\). Spróbujemy obliczyć wartość \(dp'[v][u][w]\) oznaczającą, na ile sposobów w poddrzewie wierzchołka \(v\) w drzewie \(T_2\) można zanurzyć drzewo powstałe przez rozcięcie drzewa \(T_1\) względem krawędzi \(uw\) i pozostawienie spójnej składowej zawierającej wierzchołek \(u\) tak, aby \(u\) był w tym zanurzeniu przypisany do \(v\). Zwróćmy uwagę, że tablica \(dp'\) ma trzy wymiary, ale tak naprawdę jest indeksowana dwiema wartościami: wierzchołkiem drzewa \(T_2\) i (skierowaną) krawędzią drzewa \(T_1\).

Innymi słowy, ukorzeniamy drzewo \(T_1\) w wierzchołku \(u\), usuwamy poddrzewo wierzchołka \(w\) i pytamy, na ile sposobów można zanurzyć otrzymane drzewo w poddrzewie wierzchołka \(v\) w drzewie \(T_2\) tak, aby wierzchołek \(u\) był przypisany do \(v\).

Ustalmy wierzchołek \(v\). Jeśli \(v\) jest liściem, to \(dp'[v][u][w]=1\), jeśli \(u\) jest liściem w drzewie \(T_1\), oraz \(dp'[v][u][w]=0\) w przeciwnym przypadku. Dalej załóżmy, że \(v\) ma \(k\) dzieci. Oznaczmy te dzieci przez \(c_1,\dots,c_k\). Załóżmy, że obliczyliśmy wartości \(dp'\) dla wszystkich dzieci \(v\) oraz wszystkich par wierzchołków z \(T_1\) połączonych krawędzią. Ustalmy wierzchołki \(u\) i \(w\) połączone krawędzią w \(T_1\). Niech \(t\) będzie liczbą sąsiadów \(u\) różnych od \(w\) w drzewie \(T_1\). Jeśli \(t=0\), to mamy \(dp'[v][u][w]=1\). Dalej załóżmy, że \(t>0\).

Jeśli \(t>k\), to \(dp'[v][u][w]=0\), gdyż nie da się zanurzyć odpowiedniego fragmentu drzewa \(T_1\) w poddrzewie wierzchołka \(v\) w drzewie \(T_2\). Dalej załóżmy, że \(t\leq k\). Niech \(s_1,\dots,s_t\) będą sąsiadami \(u\) różnymi od \(w\). Aby otrzymać zanurzenie, musimy przypisać wierzchołki \(s_1,\dots,s_t\) do \(c_1,\dots,c_k\) w pewnej kolejności. Rozważmy pewne takie przypisanie. Niech \(p_1,\dots,p_t\) będzie ciągiem parami różnych dzieci wierzchołka \(v\) i załóżmy, że wierzchołkowi \(s_i\) przypisujemy wierzchołek \(p_i\). Wówczas liczba zanurzeń wynosi \[ \prod_{i=1}^t dp'[p_i][s_i][u], \] gdyż dla każdego wierzchołka \(s_i\) musimy zanurzyć odpowiedni fragment drzewa \(T_1\) otrzymany po obcięciu krawędzi \(us_i\) w poddrzewie wierzchołka \(p_i\) oraz takie zanurzenia są od siebie niezależne. Aby obliczyć wartość \(dp'[v][u][w]\), musimy zsumować wartości dla wszystkich możliwych przypisań (i wziąć modulo \(M\)). Liczba wszystkich takich przypisań wynosi \(O(1)\), gdyż stopnie wierzchołków są ograniczone.

Otrzymujemy zatem algorytm, który oblicza tablicę \(dp'\) w czasie \(O(n\cdot m)\), ponieważ liczba krawędzi w drzewie \(T_1\) jest ograniczona przez \(n-1\). Teraz opiszmy, w jaki sposób na podstawie tablicy \(dp'\) możemy obliczyć wynik.

Rozważmy pewne zanurzenie drzewa \(T_1\) w drzewie \(T_2\). Zauważmy, że wówczas jednoznacznie wyznaczony jest wierzchołek drzewa \(T_1\), który przechodzi na wierzchołek drzewa \(T_2\) znajdujący się najbliżej korzenia \(T_2\). Dlaczego? Jeśli mamy dwa różne wierzchołki \(u\) i \(v\) w drzewie \(T_1\) takie, że przechodzą one na dwa różne wierzchołki \(x\) i \(y\) w drzewie \(T_2\) oraz \(x\) i \(y\) są oddalone od korzenia \(T_2\) o tyle samo, to wierzchołek \(z\) będący najniższym wspólnym przodkiem \(x\) oraz \(y\) znajduje się bliżej korzenia \(T_2\) niż wierzchołki \(x\) i \(y\). Ponadto \(z\) leży na jedynej ścieżce między \(x\) i \(y\). Ze spójności drzewa \(T_1\) wiemy więc, że pewien wierzchołek drzewa \(T_1\) przechodzi na wierzchołek \(z\). Stąd jeśli mielibyśmy dwa różne wierzchołki w drzewie \(T_1\), które przechodzą na dwa różne wierzchołki położone najbliżej korzenia \(T_2\), to w \(T_1\) mielibyśmy wierzchołek przechodzący na wierzchołek znajdujący się jeszcze bliżej korzenia \(T_2\). Otrzymujemy sprzeczność.

Możemy więc postąpić następująco: Przeiterujemy się po wszystkich wierzchołkach \(v\) drzewa \(T_2\) oraz po wszystkich wierzchołkach \(u\) drzewa \(T_1\). Dla każdej pary wierzchołków obliczymy liczbę zanurzeń drzewa \(T_1\) ukorzenionego w \(u\) w poddrzewie wierzchołka \(v\) w drzewie \(T_2\) ukorzenionym w \(v\). Dzięki powyższemu faktowi wiemy, że jeśli zsumujemy te wartości po wszystkich parach wierzchołków \(u\) i \(v\), żadne zanurzenie nie zostanie zliczone więcej niż raz.

Ustalmy więc wierzchołki \(v\) oraz \(u\). Niech \(k\) będzie liczbą dzieci wierzchołka \(v\) w \(T_2\) a \(c_1,\dots,c_k\) będą tymi dziećmi i niech \(t\) będzie liczbą sąsiadów wierzchołka \(u\) w \(T_1\) oraz niech \(s_1,\dots,s_t\) będą tymi sąsiadami. Jeśli \(t>k\), to nie możemy zanurzyć drzewa \(T_1\) ukorzenionego w \(u\) w poddrzewie wierzchołka \(v\) ukorzenionym w \(v\). W przeciwnym przypadku, analogicznie do sytuacji, w której obliczaliśmy tablicę \(dp'\), musimy rozważyć wszystkie przypisania wierzchołków \(s_1,\dots,s_t\) do wierzchołków \(c_1,\dots,c_k\). Niech \(p_1,\dots,p_t\) będzie ciągiem parami różnych dzieci wierzchołka \(v\). Załóżmy, że wierzchołkowi \(s_i\) przypisujemy wierzchołek \(p_i\). Wówczas liczba zanurzeń wynosi \[ \prod_{i=1}^t dp'[p_i][s_i][u], \] gdyż dla każdego wierzchołka \(s_i\) musimy zanurzyć odpowiedni fragment drzewa \(T_1\) otrzymany po obcięciu krawędzi \(us_i\) w poddrzewie wierzchołka \(p_i\) oraz takie zanurzenia są od siebie niezależne. Aby obliczyć liczbę zanurzeń drzewa \(T_1\) ukorzenionego w \(u\) w poddrzewie wierzchołka \(v\), musimy zsumować wartości dla wszystkich możliwych przypisań (i wziąć modulo \(M\)). Liczba takich przypisań wynosi \(O(1)\), gdyż stopnie wierzchołków są ograniczone.

Otrzymaliśmy więc rozwiązanie działające w złożoności \(O(n\cdot m)\), co pozwala na rozwiązanie zadania w pełni.

Na końcu możemy dodać jeszcze drobną uwagę co do implementacji tego rozwiązania. Przy obliczaniu wartości \(dp'\) oraz wyniku końcowego musimy przechodzić przez wszystkie możliwe przypisania sąsiadów pewnego wierzchołka z \(T_1\) do dzieci pewnego wierzchołka z \(T_2\). Zauważmy, że ukorzeniając drzewo \(T_2\) w wierzchołku o stopniu mniejszym od \(3\), możemy zapewnić, że żaden wierzchołek z \(T_2\) nie będzie miał więcej niż dwoje dzieci. Dzięki takiej obserwacji, możemy łatwo wypisać wszystkie przypadki przypisań sąsiadów wierzchołka z \(T_1\) do dzieci wierzchołka z \(T_2\) dla różnych liczb tych dzieci i sąsiadów. Widzimy bowiem, że interesują nas tylko przypadki, gdy liczba sąsiadów w \(T_1\) jest nie większa od liczby dzieci w \(T_2\), a ta nie przekracza 2. Dzięki temu możemy przejść przez wszystkie możliwe przypisania bardzo efektywnie zamiast generować je na bieżąco podczas wykonywania programu (na przykład za pomocą rekurencji). Takie usprawnienie nie zmienia asymptotycznej złożoności, jednak w praktyce pozwala na znaczne przyspieszenie działania programu poprzez zmniejszenie stałej ukrytej w notacji \(O\).