Omówienie zadania Midas (III etap XXIV OI)

Wstęp

W tym zadaniu mamy dane drzewo binarne o \(n\) wierzchołkach, ponumerowanych liczbami od \(1\) do \(n\). Korzeń drzewa znajduje się w wierzchołku o numerze \(1\). Niech \((x,y)\) oznacza taką krawędź pomiędzy \(x\) i \(y\), że \(x\) jest ojcem \(y\). Każdej krawędzi \((x,y)\) przypisana jest waga \(w(x,y)\) według następującej reguły:

  • jeśli \(y\) jest lewym synem \(x\), to \(w(x,y)\) jest równe sumie wag na ścieżce od \(1\) do \(x\),
  • jeśli \(y\) jest prawym synem \(x\), to \(w(x,y)\) jest równe sumie wag na ścieżce od \(1\) do \(x\) powiększonej o \(1\).

Dla każdego wierzchołka \(x\), jego kosztem \(k(x)\) nazwiemy sumę wag na ścieżce od korzenia do \(x\). Zadanie polega na odpowiedzeniu na \(z\) zapytań postaci: Czy \(k(x) \ge k(y)\)?

Przykładowe drzewo binarne z obliczonymi wagami krawędzi i kosztami.

Rozwiązanie \(O(z \cdot n)\)

Lemat 1. Niech \(c(x)\) oznacza słowo składające się z zer i jedynek odpowiadające ścieżce od \(1\) do \(x\). Mianowicie niech każde \(0\) odpowiada krawędzi w lewo, a każda \(1\) odpowiada krawędzi w prawo na tej ścieżce. Np. dla drzewa z powyższego rysunku: \(c(4) = 001\), a \(c(7) = 0100\). Wówczas \(c(x)\) jest binarną reprezentacją liczby \(k(x)\) (po pominięciu zer wiodących).

Dowód. Dowód przez indukcję. Na początku sprawdźmy przypadki brzegowe. Dla korzenia, \(c(1)\) jest słowem pustym (które możemy uznać za równoważne liczbie zero) i \(k(1) = 0\). Dla lewego syna korzenia, \(c(x) = 0\) i \(k(x) = 0\). Dla prawego syna korzenia, \(c(x) = 1\) i \(k(x) = 1\).

Teraz czas na krok indukcyjny. Weźmy dowolny wierzchołek \(y\) niebędący korzeniem. Niech \(x\) będzie jego ojcem. Z założenia indukcyjnego \(c(x)\) jest reprezentacją binarną \(k(x)\).

  • Jeśli \(y\) jest lewym synem \(x\), to \(k(y) = k(x) + w(x, y) = k(x) + k(x) = 2k(x)\). Skoro \(c(x)\) jest binarną reprezentacją liczby \(k(x)\), to \(c(y) = c(x) \cdot 0\) (gdzie \(\cdot\) oznacza konkatenację słów) jest binarną reprezentacją liczby \(2k(x)\). Zatem \(c(y)\) jest binarną reprezentacją liczby \(k(y)\).
  • Analogicznie, jeśli \(y\) jest prawym synem \(x\), to \(k(y) = k(x) + w(x, y) = 2k(x) + 1\), natomiast \(c(y) = c(x) \cdot 1\) jest binarną reprezentacją liczby \(2k(x) + 1 = k(y)\), co kończy dowód. \(\square\)

Algorytm

Korzystając z lematu 1 uzyskujemy następujące rozwiązanie:

  1. Wczytujemy całe drzewo, dla każdego wierzchołka pamiętając numer jego lewego syna, numer jego prawego syna oraz numer jego ojca.
  2. Dla każdego zapytania \((x, y)\) przechodzimy ścieżkę od \(x\) do \(1\), zapisując przy każdym przejściu, czy idziemy lewą, czy prawą krawędzią. W ten sposób otrzymujemy \(c(x)\) po odwróceniu kolejności krawędzi (w naszym algorytmie przechodzimy drzewo od liścia do korzenia, a \(c(x)\) odpowiada ścieżce od korzenia do liścia). Analogicznie obliczamy \(c(y)\).
  3. Wypisujemy TAK, jeśli \(c(x)\) reprezentuje nie mniejszą liczbę niż \(c(y)\) w zapisie binarnym.

Uwaga

Słowa \(c(x)\) i \(c(y)\) mogą reprezentować liczby rzędu \(2^{1\,000\,000}\), więc ich wartość liczbowa nie zmieści się w zmiennej typu int, ani żadnym innym podstawowym typie danych w C++. Jednak, aby porównać \(c(x)\) i \(c(y)\) nie musimy ich zamieniać na liczby. Wystarczy najpierw porównać długości słów po usunięciu zer wiodących — dłuższe słowo odpowiada większej liczbie. W przypadku słów równej długości, przechodzimy cyfry od lewej do prawej i pierwsza pozycja, na której słowa \(c(x)\) i \(c(y)\) się różnią, determinuje zależność pomiędzy całymi liczbami.

Złożoność

Odpowiedź na każde zapytanie wymaga przejścia w drzewie ścieżki długości \(O(n)\), a następnie porównania dwóch słów długości \(O(n)\). Zatem całe rozwiązanie działa w czasie \(O(z \cdot n)\).

Rozwiązanie wzorcowe \(O(n + z)\)>

Niech \(D\) oznacza drzewo z treści zadania. Oznaczmy przez \(Z\) zbiór wierzchołków leżących na najdłuższej ścieżce idącej „tylko w lewo" od korzenia drzewa. Ponadto, niech \(P = \{P_1, P_2, \ldots\}\) oznacza zbiór poddrzew zaczepionych jako prawi synowie wierzchołków ze zbioru \(Z\).

Przykładowe drzewo \(D\), którego zbiór \(Z=\{1, 2, 3\}\), korzeniem \(P_1\) jest \(4\), korzeniem \(P_2\) jest \(5\), zaś korzeniem \(P_3\) jest \(9\).

Stwórzmy obiekt \(T\) (który nazwiemy sklejonym drzewem) poprzez „nałożenie" na siebie drzew ze zbioru \(P\) w następujący sposób:

  • Wszystkie korzenie drzew z \(P\) są równoważne (w przykładzie wierzchołki \(4, 5, 9\)).
  • Wszyscy lewi synowie korzeni drzew z \(P\) są równoważni (w przykładzie wierzchołki \(6\) i \(10\)).
  • Wszyscy prawi synowie korzeni drzew z \(P\) są równoważni (w przykładzie tylko wierzchołek \(12\)).
  • \(\ldots\)
  • Ogólnie, wierzchołki \(x\) i \(y\) są równoważne, jeśli w drzewie \(P_{x'}\) zawierającym wierzchołek \(x\) ścieżka od korzenia tego drzewa do wierzchołka \(x\) ma taki sam kształt, jak ścieżka od korzenia do wierzchołka \(y\) w drzewie \(P_{y'}\) zawierającym wierzchołek \(y\).
  • Z każdego zbioru wierzchołków równoważnych wybieramy jednego reprezentanta.
  • Łączymy reprezentantów w drzewo \(T'\) na podstawie ich pozycji w oryginalnych drzewach \(P_i\).
  • Dla każdego z pozostałych wierzchołków pamiętamy dowiązanie do jego reprezentanta w drzewie \(T'\).

W ten sposób, dla każdego wierzchołka spoza zbioru \(Z\) znamy jego pozycję w sklejonym drzewie \(T\) (tożsamą z pozycją jego reprezentanta w drzewie \(T'\)).

Rysunek przedstawia sklejone drzewo \(T\) dla drzewa z treści zadania. Krawędzie nieskierowane oznaczają krawędzie drzewa \(T'\). Krawędzie skierowane przerywane prowadzą od wierzchołka spoza \(T'\) do jego reprezentanta w \(T'\).

Lemat 2. Wierzchołki zrównoważnione podczas tworzenia sklejonego drzewa \(T\) mają taki sam koszt. Wierzchołki ze zbioru \(Z\) (zbioru zerowego) mają koszt \(0\).

Dowód. Drugie zdanie lematu jest oczywiście prawdziwe, gdyż wierzchołki ze zbioru \(Z\) leżą na ścieżce idącej „tylko w lewo" od korzenia i wszystkie krawędzie na tej ścieżce mają wagę \(0\). Weźmy dowolne dwa zrównoważnione wierzchołki \(x\) i \(y\). Mają one taką samą pozycję w odpowiadających im poddrzewach \(P_x\) i \(P_y\), zatem odpowiadające im słowa \(c(x)\) i \(c(y)\) mają taką samą końcówkę. W obu przypadkach końcówka ta jest poprzedzona pewnym ciągiem zer i pojedynczą jedynką, zatem \(c(x)\) i \(c(y)\) reprezentują binarnie tę samą liczbę. Tak więc, na mocy lematu 1, wierzchołki \(x\) i \(y\) mają ten sam koszt. \(\square\)

Lemat 3. Koszt wierzchołka \(x\) należącego do drzewa \(T'\) wynosi \(2^i + j\), gdzie \(i\) to numer wiersza \(x\) w drzewie \(T'\) (liczony od \(0\)), a \(j\) to pozycja \(x\) w \(i\)-tym wierszu pełnego drzewa binarnego (liczona od lewej, od \(0\)), jeśli potraktujemy drzewo \(T'\) jako poddrzewo pełnego drzewa binarnego.

Dowód. Dowód przez indukcję. Koszt korzenia drzewa \(T'\) wynosi \(2^0 + 0 = 1\). Weźmy dowolny wierzchołek \(y\) niebędący korzeniem drzewa \(T'\). Niech \(x\) będzie jego ojcem. Z założenia indukcyjnego \(k(x) = 2^{i_x} + j_x\). Jeśli \(y\) jest lewym synem \(x\), to \(k(y) = 2k(x) = 2^{i_x + 1} + 2j_x = 2^{i_y} + j_y\). Jeśli \(y\) jest prawym synem \(x\), to \(k(y) = 2k(x) + 1 = 2^{i_x + 1} + (2j_x + 1) = 2^{i_y} + j_y\). \(\square\)

Przykładowe pełne drzewo binarne z podaną wartością kosztu, numerem wiersza i numerem w obrębie warstwy dla każdego wierzchołka.

Wniosek

Na mocy lematu 2, aby porównać koszty dowolnych dwóch wierzchołków \(x\) i \(y\), możemy najpierw sprawdzić, czy któryś z nich nie jest wierzchołkiem zerowym (wówczas jego koszt jest równy \(0\)). Jeśli żaden z wierzchołków nie jest wierzchołkiem zerowym, wtedy wystarczy, że porównamy koszty ich reprezentantów w drzewie \(T'\). Co więcej, na mocy lematu 3, każdy wierzchołek w wierszu \(i\) ma koszt większy od każdego wierzchołka w poprzednich wierszach. Zatem, aby porównać dwa wierzchołki z drzewa \(T'\) wystarczy najpierw sprawdzić, czy leżą w tym samym wierszu i jeśli leżą w różnych wierszach, to wierzchołek w niższym wierszu ma większy koszt, a jeśli leżą w tym samym wierszu, to prawy wierzchołek ma większy koszt od lewego.

Algorytm

Preprocessing:

  1. Znajdujemy zbiór \(Z\) i zbiór korzeni drzew ze zbioru \(P\).
  2. Tworzymy sklejone drzewo \(T\) w następujący sposób:
    1. Zaczynamy od pustego drzewa i „dokładamy" do niego kolejne drzewa \(P_1, P_2, \ldots\).
    2. Dla każdego drzewa \(P_i\) przechodzimy BFS-em ze zmienną \(x\) po jego wierzchołkach, równolegle przechodząc ze zmienną \(y\) po odpowiadających \(x\) wierzchołkach w drzewie \(T'\).
    3. Jeśli w miejscu wskazywanym przez zmienną \(y\) nie ma jeszcze wierzchołka w drzewie \(T'\), to dodajemy w tym miejscu do drzewa \(T'\) wierzchołek o numerze wskazywanym przez zmienną \(x\) w drzewie \(P_i\).
    4. Jeśli w miejscu wskazywanym przez \(y\) jest już wierzchołek w drzewie \(T'\), to nie zmieniamy drzewa \(T'\), ale ustawiamy \(y\) jako reprezentanta wierzchołka \(x\).
  3. Przechodzimy BFS-em wszystkie wierzchołki drzewa \(T'\) i nadajemy im kolejność zgodnie z tym przejściem. Kolejność ta odpowiada rosnącym kosztom — w każdym wierszu występują wierzchołki o większych kosztach niż w poprzednim wierszu, a w ramach wiersza koszty rosną od lewej do prawej.

Zapytania:

  1. Dla każdego zapytania \((x,y)\) w czasie stałym sprawdzamy, czy któryś z wierzchołków nie jest wierzchołkiem zerowym i jeśli nie, to zwracamy wynik zgodny z obliczoną wcześniej kolejnością dla reprezentantów wierzchołków \(x\) i \(y\).

Złożoność

Krok 1 i 3 preprocessingu (szukanie zbioru \(Z\) i korzeni drzew ze zbioru \(P\) oraz przejście BFS-em drzewa \(T'\)) wykonujemy w czasie \(O(n)\). Krok 2 preprocessingu (tworzenie sklejonego drzewa \(T\)) również wykonujemy w czasie \(O(n)\): do dołączenia pojedynczego drzewa \(P_i\) potrzebujemy czasu liniowego względem rozmiaru tego drzewa, więc łącznie potrzebujemy czasu liniowego względem sumy rozmiarów drzew \(P_i\), czyli liniowego względem \(n\). Na każde zapytanie odpowiadamy w czasie stałym. Zatem łączna złożoność czasowa algorytmu wynosi \(O(n + z)\).