TODO: Stromové algoritmy - LCA, Heavy-light, centroidová dekompozice

[vvolhejn]

Jedna z věcí která se docela blbě píše i když má člověk řešení vymyšlené:

• LCA (Lowest Common Ancestor) se dost používá v případech, kdy se odpovídá na dotazy na cesty, (které pak dokážeme složit ze dvou částí). Taky je předpokladem pro Heavy-light
• Heavy-light - všichni o tom mluví, jako by to bylo nějak hrozné, ale samotný základ je dost jednoduchý. Spíš jde o to, že pak využívá jiné věci, jako právě LCA, nebo hromadu segtree.
• Centroidová dekompozice - zase, je hlavně dlouhá. (Úloha z Polska mi takhle vyšla na 140 řádků. Možná to ale bylo úlohou.) Kostra metody je v zásadě dost daná a mění se jen málo:
  • Najít centroid grafu
  • Zakořenit v centroidu, provést nějaké výpočty většinou přes DFS (obsah DFS už záleží na úloze)
  • Centroid nějak označit a rekurzivně se zavolat na jednotlivé podstromy