某岛

… : "…アッカリ~ン . .. . " .. .
August 30, 2011

SPOJ 375. Query on a tree

Brief description :

动态维护树中两点之间路径上边权的最大值。

Tags: Classical

Analysis :

经典问题.. . 树链剖分 300- 行,3.10+ s
动态树 150- 行。。。 2.90+ s…

(目前 Yang Zhe 作业里的 全局平衡二叉树 还不知道怎么实现。>_<。) 树链剖分(。。过去的写法。。。3s+-。。。
上面是我最开始时的写法。。写的非常小心谨慎。。。上来就分别对结点、边、路径各定义了一组结构体。。。(Vertex, Edge, Path … 然后全程指针指来指去。。
点和边各有一个 host 指针。。(点寄宿在边上。。边寄宿在重路径上。。。
。。路径的本体是一棵线段树,(。。为了刷榜还特地写成了自下向上维护的形式。(因为有剪枝。。。。
。然后记录其最高点的 Vertex 的指针。。(。head。。(。。跳链和询问的时候计算 offset 都要用到。。。
。。

树链剖分(。。。现在的写法。。3s+-。。。
.. 只保留的 path 这一个结构体。。直接记录每个点所在的路径。。。

External link:

https://www.spoj.pl/problems/QTREE/