树链剖分

基本知识

树链剖分是一种可以将树上问题转化为序列问题的思想，将树分割为若干条链，以维护树上的路径信息。

树链剖分有多种形式，例如重链剖分，长链剖分，实链剖分。本文主要介绍重链剖分。

重子节点：

fa[u]，存储 u 的父亲节点。

dep[u]，存储 u 在树中的深度。规定根节点的深度为 1。

siz[u]，存储以 u 为根的子树大小，包含 u 这个节点。

son[u]，存储 u 的重儿子，即 u 的所有儿子 v 中 size_v 最大的一个儿子。

top[u]，存储 u 节点所在的重链中深度最浅的节点（即重链的顶端）。

dfn[u]，存储 u 节点在 DFS 序中的位置。

rnk[u]，存储 DFS 序中的第 i 个位置对应在树上的编号。有 rnk_{dfn_u} = u。

模板题。