SPOJ 2798. Query on a tree again!

Brief description:

… 詢問從根結點到某結點的路徑上第一個黑點。。。

Analysis:

。。這題方法非常多了。。樹鏈剖分或是動態樹均可。。。
。(。。不過樹狀數組直接維護 DFS 序列,然後用倍增祖先似乎更直接。。

動態樹。。(8.5s 。。。
樹狀數組。。(8.2s 。。。

External link:

http://www.spoj.pl/problems/QTREE3/