基本知识
树链剖分是一种可以将树上问题转化为序列问题的思想，将树分割为若干条链，以维护树上的路径信息。
树链剖分有多种形式，例如重链剖分，长链剖分，实链剖分。本文主要介绍重链剖分。
基本定义
重子节点：
预备数组
fa[u]，存储 $u$ 的父亲节点。
dep[u]，存储 $u$ 在树中的深度。规定根节点的深度为 $1$。
siz[u]，存储以 $u$ 为根的子树大小，包含 $u$ 这个节点。
son[u]，存储 $u$ 的重儿子，即 $u$ 的所有儿子 $v$ 中 $size_v$ 最大的一个儿子。
top[u]，存储 $u$ 节点所在的重链中深度最浅的节点（即重链的顶端）。
dfn[u]，存储 $u$ 节点在 $\text{DFS}$ 序中的位置。
rnk[u]，存储 $\text{DFS}$ 序中的第 $i$ 个位置对应在树上的编号。有 $rnk_{dfn_u}=u$。
两遍 DFS
例题讲解
树链剖分 - 题单 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
【模板】重链剖分/树链剖分
模板题。