某岛

… : "…アッカリ~ン . .. . " .. .
July 31, 2012

SPOJ 2798. Query on a tree again!

Brief description:

… 询问从根结点到某结点的路径上第一个黑点。。。

Analysis:

。。这题方法非常多了。。树链剖分或是动态树均可。。。
。(。。不过树状数组直接维护 DFS 序列,然后用倍增祖先似乎更直接。。

动态树。。(8.5s 。。。
树状数组。。(8.2s 。。。

External link:

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