树链剖分

树链剖分可以将一棵树剖分成若干条链，并使一条链上的 dfn（即dfs序）连续，然后用其他的数据结构维护信息。

一般来说树链剖分即为重链剖分 。

重子结点 表示其子结点中子树最大的子结点中的一个。其余子节点为轻子结点。

我们第一次 dfs 计算出：

• $\operatorname{fa}(x)$ 表示结点 $x$ 在树上的父亲。
• $\operatorname{dep}(x)$ 表示结点 $x$ 在树上的深度。
• $\operatorname{siz}(x)$ 表示结点 $x$ 的子树的结点个数。
• $\operatorname{son}(x)$ 表示结点 $x$ 的 重儿子。

第二次 dfs 计算出：

• $\operatorname{top}(x)$ 表示结点 $x$ 所在 重链 的顶部结点（深度最小）。
• $\operatorname{dfn}(x)$ 表示结点 $x$ 的 DFS 序，也是其在线段树中的编号。
• $\operatorname{rnk}(x)$ 表示 DFS 序所对应的结点编号，有 $\operatorname{rnk}(\operatorname{dfn}(x))=x$。

void dfs1(int u,int f){
    fa[u]=f;
    dep[u]=dep[f]+1;
    siz[u]=1;
    for(int i=frm[u];i;i=nxt[i]){
        int v=to[i];
        if(v==f)continue;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]])son[u]=v;
    }
}
void dfs2(int u,int ftop){
    top[u]=ftop;
    dfn[u]=++idx;
    rnk[idx]=u;
    if(son[u])dfs2(son[u],top[u]);
    for(int i=frm[u];i;i=nxt[i]){
        int v=to[i];
        if(v!=son[u]&&v!=fa[u])dfs2(v,v);
    }
}

重链内的 DFS 序是连续的。一棵子树内的 DFS 序是连续的。