叫复习笔记或许更好。
树链剖分就是把树剖成链去解决一些问题。
定义
- 重子节点：子节点中子树大小最大的节点。
- 轻子节点：除重子节点外的其他子节点。
- 重边：到重子节点的边。
- 轻边：到轻子节点的边。
记号
- \(dfn[x]\)：DFS 序，也是在线段树中的编号。
- \(son[x]\)：重子节点。
- \(dep[x]\)：深度。
- \(siz[x]\)：子树大小。
- \(top[x]\)：链顶。
- \(fa[x]\)：父节点。
实现
跑两边 DFS 就可以把这些信息全部求出来了。
应用
这就是精华。
维护路径信息
你会发现，每条重链的 \(dfn[x]\) 是连续的，所以我们要维护路径 \((x,y)\) 的信息时，直接暴力将节点深度最大的那个跳到链顶维护信息，直到跳到同一条链上为止。
这是路径求和的伪代码。
\[\begin{array}{l}
\text{TREE-PATH-SUM }(u,v) \\
\begin{array}{ll}
2 & \textbf{while }u.top\text{ is not }v.top \\
3 & \qquad \textbf{if }u.top.deep< v.top.deep \\
4 & \qquad \qquad \text{SWAP}(u, v) \\
5 & \qquad tot\gets tot + \text{sum of values between }u\text{ and }u.top \\
6 & \qquad u\gets u.top.father \\
7 & tot\gets tot + \text{sum of values between }u\text{ and }v \\
8 & \textbf{return } tot
\end{array}
\end{array}
\]
维护子树信息
你会发现，一棵子树内的 \(dfn[x]\) 是连续的，所以我们只需要修改 \(dfn[x],\dots,dfn[x]+siz[x]-1\) 的信息即可。
求最近公共祖先
不断向上跳重链，当跳到同一条重链上时，深度较小的结点即为 LCA。
向上跳重链时需要先跳所在重链顶端深度较大的那个。
扩展
点权->边权？
有的题目不再要求维护节点上的信息而是边上的，这种该如何操作？
很简单，把 \((x,y)\) 这条边的信息赋给深度更小的那个节点，然后正常做就好了，正确性显然。
咕咕咕