对于序列上线性结构,我们可以很轻松的用一些数据结构来维护区间的某些信息。

但是对于树上的结构,对于不需修改的情况下,可以用树上倍增和树上差分很轻松的维护。 但对于需要修改的情况,倍增和差分就难以解决了。

这时候我们就需要一个更加有效的方法来维护,就是树链剖分。

树链剖分的本质依旧是对于(u,v)(u, v)路径进行查询。

我们将边划分成重边和轻边。 并且对于每个点用DFS序作为他在线段树下的下标

一个边(u,v)(u, v)为重边,当vvuu所有儿子中节点最多的点。除重边以外的都是轻边。可以看出,对于一条重链(由重边连续组成的边) 很显然点皆为连续的。

那么对于(u,v)(u, v)的询问,我们不断的倍增跳上去,并且用线段树来维护我们所求的信息即可。具体参考倍增跳上去的代码
BZOJ 1036 树的统计

树链剖分模板题

Luogu 4114 Qtree1

同样的树链剖分但是这次点权改成边权,注意到对于一条边(u,v)(u, v)我们可以将它下放到他的vv节点作为点权,那么同样的步骤做即可。要注意对于路径(u,v)(u,v),
lca(u,v)lca(u, v) 是不能算的,因为它代表上一条边。