树链剖分

分为重链剖分和长链剖分以及其他奇怪的剖分。以重剖为主。

重链剖分

将树上问题重链剖分为序列问题（经常是 DFS 序）然后用数据结构（经常是线段树）维护。

剖分部分

定义：

• 重儿子：对于一个点，其儿子中，子树最大的那个；
• 重边：父亲到重儿子的连边；
• 轻儿子：除了重儿子以外的儿子；
• 轻边：父亲到轻儿子的连边。

证明一个东西：一条链上（不是路径，虽然差不多，路径就是两条链拼起来）至多有 \(\log n\) 条轻边。

很显然，每次若是走轻边，子树大小都至少会减少一半，所以至多走 \(\log n\) 次就到底了。

于是我们即使暴力维护轻边的复杂度都是 \(O(F(n)\log n)\) 的，\(F(n)\) 是数据结构单点操作复杂度。

而由于重边在儿子中的唯一性，所以所有的重边形成了若干条链，不妨称之重链。

一条链上包含多条重链。由于轻重边的交替排布，重链的数量级也是 \(\log n\) 的。考虑到大部分数据结构维护的是下标连续的区间，于是这里有一个小 trick，DFS 求 dfn 时，优先走重边，这样重链上的下标就连续了，所以我们只要做一次数据结构的区间操作即可维护重边上的信息，记 \(top(u)\) 为包含 \(u\) 的重链的链头，则每次跳 \(u\to fa(top(u))\) 即可一次跳过一条重链加一条轻边，时间复杂度 \(O(F'(n)\log n)\)，\(F'(n)\) 为数据结构区间操作复杂度，对于线段树这种的，\(F'(n)\doteq F(n)\)。

综上对于一条链的操作，复杂度就为 \(O(F(n)\log n)\)。

例题：

给你一棵带边权树，支持下列操作：

• 查询子树和
• 查询 \(u,v\) 路径和
• 修改子树边权
• 修改路径边权

先 DFS 出 dfn，然后操作 1、3 对应了一段连续的区间，直接线段树区间操作即可；操作 2、4 首先将路径拆成两条链 \((u,\text{lca}),(\text{lca},v)\)，然后分别剖即可。时间复杂度分别为 \(O(\log n),O(\log^2 n)\)。

实现

第一遍 DFS 求出以下信息：

• \(dep(u)\)：\(u\) 的深度；
• \(siz(u)\)：\(u\) 子树大小；
• \(son(u)\)：\(u\) 的重儿子；
• \(fa(u)\)：\(u\) 的父亲。

void dfs1(int u,int Fa){
    dep[u]=dep[Fa]+1;
    fa[u]=Fa;
    int mxson,mxsiz=0;
    for(edge v:e[u]){
        if(v.v!=fa){
            dfs1(v.v,u);
            siz[u]+=siz[v.v];
            if(siz[v.v]>mxsiz)
                mxsiz=siz[v.v],mzson=v.v;
        }
    }
    son[u]=mxson;
}

第二遍 DFS 求出以下信息：

• \(top(u)\)：包含 \(u\) 的重链链头；
• \(dfn(u)\)：\(u\) 的 dfn；
• \(idx(u)\)：\(u\) 的 dfn 逆向索引。

void dfs2(int u,int t){
    top[u]=t;
    dfn[u]=++dfncnt;
    idx[dfncnt]=u;
    if(top[son[u]]!=t) dfs2(son[u],son[u]);
    else dfs2(son[u],t);
    for(edge v:e[u]){
        if(v.v!=fa[u]&&v.v!=son[u]){
            dfs2(v.v,v.v); // 轻儿子肯定不在 u 的重链上
        }
    }
}

修改路径：

void modify_chain(int u,int v,int x){
    int fu=u,fv=v;
    while(top[fu]!=top[fv]){
        if(dep[top[fu]]<dep[top[fv]]) swap(fu,fv); 
        modify(1,1,n,dfn[top[fu]],dfn[fu],x);
        fu=fa[top[fu]]; // 每次选深的跳直到到同一重链上
    }
    if(dep[fu]>dep[fv]) swap(fu,fv);
    modify(1,1,dfn[fu],dfn[fv],x);
}

查询路径：

int query_chain(int u,int v,int x){
    int fu=u,fv=v,res=0;
    while(top[fu]!=top[fv]){
        if(dep[top[fu]]<dep[top[fv]]) swap(fu,fv); 
        res+=query(1,1,n,dfn[top[fu]],dfn[fu],x);
        fu=fa[top[fu]]; // 每次选深的跳直到到同一重链上
    }
    if(dep[fu]>dep[fv]) swap(fu,fv);
    res+=query(1,1,dfn[fu],dfn[fv],x);
    return res;
}

特殊的，如果信息在点上，则可以把信息转移到边 \((u,fa(u))\) 上。