题目链接


一、思路解析

给出一棵树,要求按顺序走完给定的所有点,每移动一步就要给这次移动经过的点增加$1$的点权。求每一个点的最小点权。
显然这是一个树上差分的题目,因为树上两点之间有且仅有一条最短路。并且,只有每一步都走最短路,最终的答案才会是最优(树上两点间无论如何走,经过的边组成的边集一定包含最短路上的所有点)。

1、LCA(倍增法)

不知道倍增是个啥的同志们可以先看看这题
$LCA$的倍增求法和$ST$表一样,都是需要先进行一次$O(N\log N)$的预处理。只是求$LCA$的时间复杂度是$O(\log N)$,和$ST$表不同。这也不难理解,$ST$表是在区间(链)上的,而求$LCA$是在树上的,不能通过简单代数加减求得。
倍增求$LCA$有两步预处理,分别是一次$DFS$(弄清楚各个点的父节点以及深度),和一次递推计算(感觉像$DP$一样。)