重链剖分 / 树链剖分 题解

思路

小规模可以在每次操作时直接枚举路径或子树。若树是编号顺序的一条链，则路径和子树都对应数组区间；若只有子树操作，则一次 DFS 的欧拉序也能把每棵子树变成连续区间。这两个特殊结构都可以直接使用区间加、区间求和数据结构。

一般树上的路径不一定是一个欧拉序区间。重链剖分把每个结点选择一个子树最大的儿子作为重儿子，其余儿子为轻儿子。沿重边形成若干条重链，并优先访问重儿子生成 DFS 序。这样每条重链在 DFS 序中连续，任意根到结点的路径只会跨越 $O(\log N)$ 条重链。

做法

第一次遍历求出每个结点的父亲、深度、子树大小和重儿子。第二次遍历确定每个结点所在重链的链头以及 DFS 序编号。

在线段树上按 DFS 序存放点权，并维护区间和与区间加懒标记：

• 处理路径时，只要两点链头不同，就取链头更深的一侧，把该链头到当前结点的整段交给线段树，然后跳到链头父亲；两点进入同一重链后，再处理它们之间的最后一段。
• 由于 DFS 时优先访问重儿子，一棵以 $x$ 为根的子树恰好对应区间 $[dfn_x,dfn_x+size_x-1]$，子树修改和查询各只需一次线段树操作。

所有加法和区间和都及时对 $P$ 取模。线段树给长度为 $len$ 的区间增加 $z$ 时，区间和应增加 $z\times len$。

重链剖分路径循环每次都会跨过一条轻边。轻儿子的子树大小至多为父亲子树大小的一半，因此一条根路径上轻边数为 $O(\log N)$。每段在线段树上的操作也是 $O(\log N)$，所以路径操作满足所需复杂度。

复杂度

预处理和建树为 $O(N\log N)$。每次路径修改或查询为 $O(\log^2 N)$，每次子树修改或查询为 $O(\log N)$。空间复杂度为 $O(N)$。