【树的点分治】【ST表】BZOJ 3784 —— 树上的路径
总有一个序列，能够满足题目中所需求的一切性质。—— 鲁迅
（没说过）
这里引入一个叫做点分治序列的东西,它通过下列步骤生成.
1.找到当前树的重心,将重心加入序列.
2.从重心出发,dfs遍历整个树,将遍历到的点加入序列.
3.将与重心相连的边断掉,生成若干子树,对于每一个子树重复上述过程.
显然,点分治序列不是唯一的.
例如下图的一个点分治序列是
对于一个已经确定的重心,我们暂时只考虑经过这个重心的路径,即从它的某一个子树中的点,到另一个子树中的某个点(也可以是这个重心).这样这条路径就被分为两段,不妨分开处理,只考虑重心到某个点的距离,对于路径而言则只需要将路径的两个端点到重心的距离相加.
因此,我们考虑确定路径的一个点,对于另一个点的选取显然是有范围限制的.即在这个点所在子树前,遍历的所有点以及目前的重心,都可以作为路径的另一个端点.
此时点分治序列的性质就体现出来了.
可以发现,能成为另一个端点的点,在点分治序列上是连续的.可以预处理出来(l,r).然后只需用ST表,即可快速询问哪一个点作为另一个端点会使得当前路径最大.塞入一个优先队列中输出答案.
接着还有一个问题,当优先队列队首所表示的路径出队后,实际上对于这个点,经过相应重心的第二长路径,第三长路径等是并没有加入队列的.
此时可以看作将点分治序列上(l,r)从最大值值处断开,分为两个区间继续处理即可将剩下的情况处理出.这也是为什么需要优先队列的原因.