树论-树链剖分

树链剖分是一种用于处理树上路径查询的算法，它将树分解为多条链，使得任意两点间的路径可以表示为若干段链的组合。

树链剖分分为 重链剖分 和 长链剖分 。

重链剖分

定义

重儿子：其儿子中子树大小最大的儿子。如有多个子树大小最大的儿子，只取一个儿子作为重儿子。

轻儿子：其儿子中不是重儿子的儿子。

重边：重儿子与其父亲的边

轻边：轻儿子与其父亲的边

重链：许多条首尾相接的重边

过程

\(f_x\) ： \(x\) 的父亲

\(dep_x\) ： \(x\) 的深度

\(si_x\) ：以 \(x\) 为根的子树大小

\(son_x\) ： \(x\) 的重儿子

第一次dfs处理出来以上信息

\(dfn_x\) ： \(x\) 的dfs序

\(idfn_x\) ： dfs序为 \(x\) 的节点编号

\(top_x\) ： \(x\) 所在的重链的顶部节点（深度最小的点）

第二次dfs处理出来以上信息

代码

第一次dfs

void dfs(int s,int fa) {
    f[s]=fa,dep[s]=dep[fa]+1,si[s]=1;
    for(int i=0; i<v[s].size(); i++) {
        int y=v[s][i];
        if(y==fa)continue;
        dfs(y,s);
        si[s]+=si[y];
        if(si[y]>si[son[s]])son[s]=y;
    }
}

第二次dfs

void hld(int s,int fa,int topp) {
    dfn[s]=++dfscnt,idfn[dfscnt]=s,top[s]=topp;
    if(son[s])hld(son[s],s,topp);
    for(int i=0; i<v[s].size(); i++) {
        int y=v[s][i];
        if(y==fa||y==son[s])continue;
        hld(y,s,y);
    }
}

性质

1.一棵子树内的dfs序是连续的。

2.整棵树的根节点到树内任意一点的路径可以被拆分成不超过 \(O(\log n)\) 条重链。

3.重链上的dfs序是连续的。

应用

维护LCA（最近公共祖先）

两个点不断向上跳重链，当两个点跳到同一条重链上时，深度较小的点为LCA。

代码

int lca(int x,int y) {
    while(top[x]!=top[y]) {
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        x=f[top[x]];
    }
    return dep[x]<dep[y]?x:y;
}

维护点权信息

维护子树的信息

根据性质1可知，任意一棵子树内的dfs序是连续的，设 \(x\) 为这棵子树的根，那么 \(dfn_x\) 到 \(dfn_x+si_x-1\) 这段区间就是子树所有节点的dfs序。

可以利用数据结构来维护区间信息。

维护路径的信息

可以把这条路径 \((x,y)\) 拆开，拆成路径 \((lca(x,y),x)\) 与路径 \((lca(x,y),y)\) 。

也就是这两个点不断向上跳重链，根据性质3可知，重链上的dfs序是连续的，跳重链的过程可以转化成区间问题。

当两个点跳到同一个重链上时，根据性质3可知，在同一个重链上时可以转化成区间问题。

可以利用数据结构来维护区间信息。

代码

int sum(int x,int y) {
    int res=0;
    while(top[x]!=top[y]) {
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        //处理 dfn[top[x]] 到 dfn[x] 的区间信息
        x=f[top[x]];
    }
    if(dep[x]<dep[y])swap(x,y);
    //处理 dfn[y] 到 dfn[x] 的区间信息
    return res;
}