Query on a tree IV

31.07.2009 - Władysław Kwaśnicki
TrudnośćTrudnośćTrudność

Zanim przejdziemy do treści i opisu rozwiązania, kilka informacji o zadaniu. Możecie je znaleźć na SPOJu (tutaj), umieścił je tam Qu Jun, ale nie jestem pewien, czy to on jest jego autorem. Niektórzy pewnie zauważyli dziwny pogrubiony napis na dole strony, w pewnym sensie to ja jestem jego sprawcą. Zadanie to udało mi się zaakceptować dopiero za 23 razem, wynikało to głównie z drobnych błędów implementacyjnych (nie należy się tym przerażać, pewnie większości z Was uda się dużo szybciej!), a po drodze spowodowałem chyba 3-krotne ponowne sprawdzenie rozwiązań - wysłałem, przeszło, poszedłem spać, rano wstaję i widzę WA... Mój program nie jest najszybszy, wierzę, że istnieje lepszy (w sensie złożoności), ale również może być tak, że po prostu moja implementacja nie jest zoptymalizowana. Jednak nawet jeżeli już wpadliście na wydajne rozwiązanie polecam doczytać do końca, znajdziecie tutaj jedną naprawdę fajną sztuczkę.

Treść

Dane jest drzewo o N wierzchołkach, które oznaczamy liczbami $ 1,2,\ldots,n $. Każda z jego $ n-1 $ krawędzi ma przyporządkowaną całkowitoliczbową wagę (być może ujemną). Dodatkowo każdy wierzchołek jest pomalowany na czarno lub biało. Na samym początku wszystkie wierzchołki są białe. Niech $ dist(a,b) $ oznacza wagę (jedynej) ścieżki między wierzchołkiem $ a $ i $ b $. Naszym celem jest (wydajne!) przetworzenie ciągu $ q $ operacji, z których każda to

  • $ C a $, zmień kolor wierzchołka $ a $ na przeciwny,

lub

  • $ A $, oblicz wagę najcięższej ścieżki między (dowolnymi) dwoma białymi wierzchołkami.

Wierzchołków oraz operacji jest co najwyżej $ 10^5 $, wagi krawędzi należą do zakresu $ [-1000 .. 1000] $.

Rozwiązanie nieoptymalne

Atak na problem rozpoczniemy od powszechnej praktyki - uproszczenia problemu. Warto zawsze zaczynać właśnie od tego, często właśnie tak można zbliżyć się do prawidłowego rozwiązania. Pamiętajcie, że autorzy zadania to też ludzie, którzy często podczas układania zadań stosują strategię "wymyśl problem, a potem postaraj się go maksymalnie utrudnić". W tym konkretnym wypadku warto na początek założyć, że każdy wierzchołek ma jakiś kolor (niekoniecznie wszystkie taki sam), a jedyną operacją, którą chcemy wykonać (tylko raz), jest $ A $. Łatwo zauważyć, że w takim wypadku algorytm musi działać w czasie $ \Omega(n) $: trzeba popatrzeć przynajmniej raz na każdy wierzchołek. A czy istnieje algorytm, który działa dokładnie w takim czasie? Tak! Z pomocą przychodzi nam tutaj programowanie dynamiczne (czy też, dla tych z Was, którzy czują się bardziej matematykami, rozumowanie indukcyjne). Bazą indukcji jest drzewo składające się z jednego wierzchołka, dla którego bez problemu możemy obliczyć odpowiedź. W kroku indukcyjnym mamy całe, być może bardzo duże, drzewo. Wybierzmy jeden z wierzchołków $ v $ i ukorzeńmy w nim drzewo. Powiedzmy, że $ v $ ma synów $ v_1, v_2, \ldots, v_k $ ($ k\geq 1 $). Możliwe są trzy sytuacje:

  1. Szukana ścieżka przechodzi przez $ v $. Możemy ją wtedy podzielić na dwie części: $ p_1 $ zawartą w podrzewie $ v_i $ i $ p_2 $ znajdującą się w poddrzewie $ v_j $ ($ i\neq j $). Każda z tych dwóch części jest najcięższą ścieżką zaczynającą się w białym wierzchołku i kończącą się w $ v $ w swoim poddrzewie.
  2. Szukana ścieżka kończy się w $ v $. Wtedy tak naprawdę jest ona najcięższą ścieżką zaczynającą się w białym wierzchołku i kończącą się w $ v $.
  3. Szukana ścieżka nie ma nic wspólnego z $ v $. Wtedy musi być całkowicie zawarta w poddrzewie wyznaczonym przez jednego z synów $ v $, czyli możemy zastosować rekurencyjnie (czy też indukcyjnie) to samo rozumowanie.

Wykorzystując te obserwacje łatwo jest stworzyć liniowe rozwiązanie bazujące na przeglądaniu w głąb. Wystarczy tylko w dowolny sposób ukorzenić całe drzewo, a następnie wyznaczać dla coraz większych poddrzew najcięższe ścieżki zaczynające się w białym wierzchołku i kończące się w korzeniu danego poddrzewa. Niech takie rozwiązanie nazywa się $ ALG $.

Trochę trudniej (ale dalej łatwo) zauważyć, że tak naprawdę to całe rozumowanie można zastosować do oryginalnego problemu, otrzymując rozwiązanie działające w czasie $ \mathcal{O}(n+qh_v\log n) $, gdzie $ h_v $ to wysokość drzewa zakorzenionego w (dowolnie wybranym) wierzchołku $ v $. Jak? Na pierwsze pytanie możemy odpowiedzieć używając $ ALG $. Następnie zmieniamy kolor jednego wierzchołka $ u $ i zastanawiamy się, na jakie wartości wyznaczane w $ ALG $ może wpłynąć taka zmiana? Okazuje się, że zmieniają się tylko wartości wyliczane na ścieżce z $ u $ do korzenia $ v $ (której długość nie przekracza $ h_v $). No dobrze, a skąd wziął się ten $ \log n $? Uaktualniając wartości na ścieżce musimy wyznaczać nowe maksima (to jest najcięższe ścieżki zaczynająca się w białym wierzchołku i kończące się w korzeniu danego poddrzewo i najcięższa ścieżka w całym poddrzewie). Możemy albo za każdym razem przeglądać wszystkich synów danego wierzchołka na ścieżce (co nie jest najlepszym pomysłem), albo pamiętać te wartości w kolejce priorytetowej lub multisecie.

By otrzymać z tego pomysłu wydajny algorytm wypadałoby znaleźć taki wierzchołek $ v $, że $ h_v\mathcal{O}(\log n) $. Czasami jest to łatwe (na przykład w pełnym drzewie binarnym), a czasami niemożliwe... Zatem trafiliśmy w ślepą uliczkę? Nic bardziej mylnego!

Fajny wierzchołek

Na chwile odpłyniemy od naszego problemu. Okazuje się, że drzewa posiadają jedną ciekawą własność: Niech $ T $ będzie dowolnym drzewem o $ n $ wierzchołkach. Istnieje taki wierzchołek $ v\in T $, że każda spójna składowa w $ T\setminus\{v\} $ ma rozmiar nie większy niż $ \frac{n}{2} $. Jak się o tym przekonać? Niech $ v $ będzie na początku dowolnym wierzchołkiem. Jeżeli nie spełnia on powyższej tezy, ma dokładnie jednego sąsiada $ u $, który należy w $ T\setminus \{v\} $ do spójnej składowej o rozmiarze przekraczającym $ \frac{n}{2} $. W takim przypadku ustalamy $ v=u $ i powtarzamy całe rozumowanie. Czy takie postępowanie musi się kiedyś skończyć? Czy też może się zdarzyć, że wpadniemy w cykl? Niech $ S_v(x) $ oznacza rozmiar składowej wierzchołka $ x $ w $ T\setminus \{v\} $. Wtedy

$$ S_u(v) + S_v(u) = n$$
$$ S_u(v) = n - S_v(u) $$
$$ S_u(v) < n - \frac{n}{2} = \frac{n}{2}$$
Reszta spójnych składowych dla $ u $ ma oczywiście rozmiar mniejszy niż $ S_v(u) $. Stąd rozmiar największej spójnej składowej cały czas się zmniejsza, zatem nasz proces musi się prędzej lub później skończyć.

No dobrze, ale właściwie po co to wszystko?

Algorytm

Skoro nie umiemy szybko wyliczać odpowiedzi w oryginalnym drzewie $ T $, zmieńmy je na inne! Ale jak?... Warto, by miało jakiś korzeń, więc powiedzmy, że tym korzeniem będzie Fajny Wierzchołek dla $ T $. Analogicznie, synami korzenia będą Fajne Wierzchołki dla powstałych spójnych składowych. Powtarzamy to rozumowanie tak długo, jak składowe mają więcej niż jeden wierzchołek (czyli tak długo, jak można je dzielić). Dla wygody oznaczmy powstałe drzewo jako $ T' $.

Łatwo zauważyć, że $ T' $ ma wysokość $ \mathcal{O}(\log n) $. Dlaczego? Każda ścieżka odpowiada w nim ciągowi coraz mniejszych spójnych składowych, z których każde dwie kolejne zawierają się w sobie, a co więcej rozmiar mniejszej nie przekracza połowy rozmiaru większej. Zauważmy też, że całe rozumowanie dotyczące tego, jak wygląda szukana ścieżka, nadal jest prawdziwe. Czyli albo ścieżka całkowicie zawiera się w którymś z poddrzew, albo kończy się w aktualnym korzeniu, albo przez niego przechodzi. Pierwszy przypadek załatwia rekursja, drugi i trzeci też daje się rozwiązać. Czyli cała idea jest taka, że chcielibyśmy przerobić algorytm działający w $ \mathcal{O}(n +q h_v \log n) $ tak, aby operował na drzewie $ T' $. Tak naprawdę jedynym problemem, jaki musimy rozwiązać, jest to, że nie potrafimy wyliczać idąc do góry w $ T' $ najdłuższej ścieżki prowadzącej do wierzchołka z jakiegoś jego poddrzewa. Skoro tego nie umiemy, to na początku działania algorytmu spamiętujemy taką informację. A dokładniej, dla każdego wierzchołka $ v $ pamiętamy jego odległości do wszystkich jego przodków w $ T' $. Mając taką informację możemy postępować podobnie jak w poprzednim rozwiązaniu, otrzymując algorytm działający w czasie $ \mathcal{O}(n\log n + q \log^2 n) $ i zużywający $ \mathcal{O}(n\log n) $ pamięci.

Podsumowanie

Cały algorytm wygląda w następujący sposób: na początku konstruujemy drzewo $ T' $. To nie jest specjalnie skomplikowane, postępujemy zgodnie ze schematem z dowodu istnienia Fajnych Wierzchołków. Ta część wymaga tylko czasu $ \mathcal{O}(n\log n) $. Dlaczego nie $ \mathcal{O}(n^2) $? Każdy wierzchołek bierze udział w co najwyżej $ \log n $ procedurach obliczania Fajnego Wierzchołka. Następnie spamiętujemy odpowiednie odległości, ten krok można łatwo połączyć z poprzedni. Mając te struktury, operacje $ A $ i $ C $ są już bardzo łatwe. W najprostszej wersji dla każdego wierzchołka $ V $ potrzebujemy trzymać:

  1. dla jego każdego syna $ u $ kopiec ze ścieżkami z $ v $ do białych wierzchołków zawartych w poddrzewie $ u $,
  2. nadrzędny kopiec przechowujący maksima z kopców dla poszczególnych synów,
  3. zmienną przechowującą aktualną odpowiedź dla poddrzewa $ v $.

Powodzenia w kodowaniu!

4.666665
Twoja ocena: Brak Ocena: 4.7 (3 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com