树链剖分

Judgelight · 2023-04-26 22:25:44 · 个人记录

树剖题的难点都不在树剖。

前言

处理树上链修改问题，我们之前使用的是差分。

但是差分的限制太大了，很多题目力不从心。

所以我们有了树链剖分。

树链剖分

我们通常指的树剖是轻重链剖分。

概念

• 重儿子：一个点 u 的重儿子 v 为 u 的所有儿子中子树节点个数最多的那个，如果个数相同任选一个。

• 重边：连接点 u 和它的重儿子 v 的边，对于每个非叶节点有且仅有一条连向儿子的重边。

• 重链：由重边构成的链，最多 \log n 条。注意单个的点也是重链。显然重链覆盖了所有的点。

• 轻边：除了重边之外的边。显然重链之间用轻边连接。

做法

第一遍 dfs 找出重边，第二遍 dfs 跑出 dfs 序和重链。

第二遍 dfs 的时候先遍历重儿子，这样可以保证在同一条重链上的点在 dfs 序上一定是连续的。

时间复杂度

假如我要修改 (u,v) 这条路径：

等价于修改 (u,lca) 和 (lca,v)。

所以只考虑 v 是 u 的祖先的情况。

可以看作修改若干条重链。

这里修改的重链数决定了我的时间复杂度。

显然重链数等价于轻边数。

每往下走一条轻边，点数至少变成 \frac{1}{2}，故最多 \log n 条。

所以时间复杂度为 O(\log n \times 区间修改时间复杂度)。

代码实现

void dfs1(int u,int from){
    depth[u]=depth[from]+1,fa[u]=from,Size[u]=1;
    for(int i=he[u];i;i=e[i].ne){
        int v=e[i].to;
        if(v==from){
            continue;
        }
        dfs1(v,u);
        Size[u]+=Size[v];
        if(Size[v]>Size[son[u]]){
            son[u]=v;
        }
    }
}
void dfs2(int u,int from,int tp){
    top[u]=tp;
    timestamps++;
    L[u]=timestamps,order[timestamps]=u;
    if(Size[u]==1){
        R[u]=timestamps;
        return ;
    }
    dfs2(son[u],u,tp);
    for(int i=he[u];i;i=e[i].ne){
        int v=e[i].to;
        if(v==from||v==son[u]){
            continue;
        }
        dfs2(v,u,v);
    }
    R[u]=timestamps;
}

void query_path(int u,int v){
    while(top[u]!=top[v]){
        if(depth[top[u]]<depth[top[v]]){
            swap(u,v);
        }
        did(L[top[u]],L[u]);
        u=fa[top[u]];
    }
    if(depth[u]>depth[v]){
        swap(u,v);
    }
    did(L[u],L[v]);
    return ;
}