树链剖分

重链剖分

【模板】重链剖分/树链剖分

upd：每条重链必定由轻儿子开始，不同重链间必定由轻边连接，重链之内必定是重边。

如果只有一次询问的话显然可以树上差分来解决，现在考虑多组询问。

处理 fa[i] dep[i] 便于询问。

处理 size[i] son[i] top[i] idx[i] f[i] 便于树剖。

明确一下树剖时变量的定义。size[i] 代表子树大小，son[i] 代表重儿子，top[i] 代表所在重链链头的原编号，idx[i] 代表 dfn 得到的新编号，f[i] 代表新编号为 i 的点的权值。

预处理过程和树剖具体实现不再赘述，重点看树剖的细节。

我们放到线段树上的是新编号，即 idx，对于线段树上下标 i，其权值为 f[i]。

对于每组询问我们不断往上跳，注意跳的过程中我们需要保存的是原编号，不能拿新编号往上跳，查询的时候则用新编号查询。

简而言之，idx[i] 只有作为线段树查询时的参数时才能用到，而 f[i] 只有作为线段树权值时才能用到，其余一律使用旧编号。

时间复杂度方面，我们以二叉树为例来解释树剖 \(O(n\log n)\) 的时间复杂度。

一.一点到根的路径上经过的重链数量不会超过 \(\log\) 条

等价于一点到根的路径上经过的轻边不会超过 \(\log\) 条。