#创作计划#浅谈长链剖分

2026-07-21 19:39:55

发布于：浙江

30阅读

0回复

0点赞

长链剖分

长链剖分是对于每一个点 $u$ ，求出它的重子节点 $h$ ，满足 $h$ 的子树中最深的节点深度最大，连接 $u \rightarrow h$ 这条重边。其他边为轻边。若干条首尾相连的重边叫做重链。如果把叶子节点也看做一条重链，那么整棵树就被划分为了若干条重链。

如图（来自 OI-WIKI）：

实现过程的伪代码如下：

function dfs1(u,f):
	fa[u]=f
	dep[u]=dep[f]+1
	maxd[u]=dep[u]
	hson[u]=0
	for v in son(u):
		if v!=f:
			dfs1(v,u)
			if maxd[v]>maxd[hson[u]]:
				hson[u]=v

function dfs2(u,t):
	top[u]=t
	if hson[u]==0:
		return
	dfs2(hson[u],t)
	for v in son(u):
		if v!=fa[u] and v!=hson[u]:
			dfs2(v,v)

性质

从根节点到叶子中，最多有 $O(\sqrt{n})$ 条轻边。

设从根节点到叶子共有 $k$ 条轻边，我们从叶子开始向根跳，设 $d_i$ 表示当跳了 $i$ 条轻边到节点 $u$ 之后， $\max_{v \in \operatorname{son}(u)}(dep_v-dep_u)$ 的值。每沿着轻边向上跳 $1$ 步，跳到的节点 $u$ 的子树大小比刚才的节点 $v$ 的子树大小至少增加了 $d_u+1$ 。也就是 $d_u \geq d_v+1$ 。
$n \geq \sum d_i \geq kd_1+\sum_{i=0}^{k-1} i=kd_1+\frac{k(k-1)}{2} \geq \frac{k(k+1)}{2}$ ，因此 $k \leq O(\sqrt{n})$ 。

不过这个没啥用，因为重链剖分是 $O(n \log n)$ 的，严格优于长链剖分的 $O(n \sqrt{n})$ 。

设 $u$ 的 $k$ 级祖先为 $p$ ，则 $p$ 所在重链的长度不低于 $k$ 。

如果 $p \rightarrow u$ 是重链，那么我们已经知道 $p \rightarrow u$ 的长度等于 $k$ 。

如果 $p \rightarrow u$ 不是重链，那么假设重链是 $p \rightarrow v$ （ $v$ 为叶子），则该链的长度一定大于 $p \rightarrow u$ 的长度，也就是大于 $k$ 。

例题1

P5903 【模板】树上 K 级祖先

给定一颗有根树， $q$ 次求 $u$ 的 $k$ 级祖先。

常用的做法是 $O(q \log n)$ 的，过不了。

设 $i$ 为自然数， $2^i \leq k<2^{i+1}$ ，我们先求 $u$ 的 $2^i$ 级祖先 $v$ ，显然这是可以预处理倍增数组 $O(1)$ 得到的。接下来，我们需要求 $v$ 的 $k-2^i$ 级祖先，由于 $k<2^{i+1}$ ，所以 $k<2^i+2^i$ ，即 $k-2^i<2^i$ 。设 $L$ 为这条重链的长度，根据性质 2， $L \geq 2^i$ ，也就是 $0 \leq k-2^i<L$ 。我们跳到 $v$ 所在链的顶端 $t$ ，设我们这个操作走了 $x$ 距离，那么我们还需要向上跳 $k-2^i-x$ 步。容易知道 $-L\leq k-2^i-x \leq L$ ，因此我们在每一个链的顶端 $t$ 的位置维护两个数组 $up_i$ 和 $down_i$ ，分别表示从 $t$ 向上 $i$ 步的点和从 $t$ 沿着重链向下 $i$ 步的点，其中 $i \leq L$ 。总时间复杂度 $O(n \log n+q)$ 。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ui unsigned int
const int MAXN=5e5+55;
struct graph{
    int nxt,to;
    graph(const int &A=0,const int &B=0):nxt(A),to(B){}
};
int n,q,u,rt,k,ans,tot=1;
ui s;
long long res;
int hd[MAXN],dep[MAXN],maxd[MAXN],hson[MAXN],tp[MAXN],len[MAXN],dist[MAXN],ju[MAXN][20];
vector<int> up[MAXN],down[MAXN];
graph edge[MAXN<<1];
ui get(ui x){
    x^=x<<13;
    x^=x>>17;
    x^=x<<5;
    return s=x;
}
void add(const int &u,const int &v){
    edge[++tot]=graph(hd[u],v);
    hd[u]=tot;
    edge[++tot]=graph(hd[v],u);
    hd[v]=tot;
    return;
}
void dfs1(const int &u,const int &fath){
    int v;
    ju[u][0]=fath;
    maxd[u]=dep[u]=dep[fath]+1;
    for(int i=1;i<=19;i++) ju[u][i]=ju[ju[u][i-1]][i-1];
    for(int i=hd[u];i;i=edge[i].nxt){
        v=edge[i].to;
        if(v!=fath){
            dfs1(v,u);
            maxd[u]=max(maxd[v],maxd[u]);
            if(maxd[v]>maxd[hson[u]]) hson[u]=v;
        }
    }
    return;
}
void dfs2(const int &u,const int &top){
    int v;
    tp[u]=top;
    len[top]++;
    if(u==top) dist[u]=0;
    else dist[u]=dist[ju[u][0]]+1;
    if(hson[u]) dfs2(hson[u],top);
    for(int i=hd[u];i;i=edge[i].nxt){
        v=edge[i].to;
        if(v!=ju[u][0]&&v!=hson[u]) dfs2(v,v);
    }
    if(u==top){
        for(int i=0,j=u,k=u;i<=len[u];i++,j=ju[j][0],k=hson[k]){
            up[u].push_back(j);
            down[u].push_back(k);
        }
    }
    return;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q>>s;
    for(int i=1;i<=n;i++){
        cin>>u;
        if(u==0) rt=i;
        else add(u,i);
    }
    dfs1(rt,0);
    dfs2(rt,rt);
    for(int i=1;i<=q;i++){
        u=(get(s)^ans)%n+1;
        k=(get(s)^ans)%dep[u];
        if(k==0){
            ans=u;
            res^=1ll*i*ans;
            continue;
        }
        u=ju[u][31-__builtin_clz(k)];
        k-=1<<31-__builtin_clz(k);
        k-=dist[u];
        u=tp[u];
        if(k>0) ans=up[u][k];
        else ans=down[u][-k];
        res^=1ll*i*ans;
    }
    cout<<res;
    return 0;
}

例题2

CF1009F Dominant Indices

给定一颗根为 $1$ 的有根树，设 $d_{u,i}$ 表示在 $u$ 的子树内到 $u$ 距离为 $i$ 的点的数量，对于每一个 $u$ ，求使得 $d_{u,i}$ 最大的 $i$ ，如果有多个取最小的 $i$ 。

不难发现 $d_{u,i}$ 的计算方法：

$d_{u,0}=1 \\ d_{u,i}=\sum_{v \in \operatorname{son}(u)} d_{v,i-1}$

设 $m$ 表示深度，这样做是 $O(nm)$ 的。

考虑长链剖分，设 $u$ 的重儿子为 $h$ ，轻儿子为 $v$ 。首先，我们利用指针，让 $d_h$ 的值直接写到 $d_u+1$ 上，更新答案 $ans_u=ans_h+1$ ；接着我们处理 $v$ 的子树，用上面的暴力递推合并答案。

分析复杂度，对于轻儿子 $v$ ，我们合并答案的复杂度是 $O(dep_v)$ 的，也就是 $v$ 所在重链的长度，而所有重链长度和为 $n$ ，因此时间复杂度为 $O(n)$ 。

代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+16;
struct graph{
    int nxt,to;
    graph(const int &A=0,const int &B=0):nxt(A),to(B){}
};
int n,u,v,*p,tot=1;
int hd[MAXN],fa[MAXN],dep[MAXN],maxd[MAXN],hson[MAXN],ans[MAXN],len[MAXN],null[MAXN<<2],*d[MAXN];
graph edge[MAXN<<1];
void add(const int &u,const int &v){
    edge[++tot]=graph(hd[u],v);
    hd[u]=tot;
    edge[++tot]=graph(hd[v],u);
    hd[v]=tot;
    return;
}
void dfs1(const int &u,const int &fath){
    int v;
    fa[u]=fath;
    maxd[u]=dep[u]=dep[fath]+1;
    for(int i=hd[u];i;i=edge[i].nxt){
        v=edge[i].to;
        if(v!=fath){
            dfs1(v,u);
            maxd[u]=max(maxd[v],maxd[u]);
            if(maxd[v]>maxd[hson[u]]) hson[u]=v;
        }
    }
    len[u]=maxd[u]-dep[u]+1;
    return;
}
void dfs2(const int &u){
    int v;
    if(hson[u]){
        d[hson[u]]=d[u]+1;
        dfs2(hson[u]);
        ans[u]=ans[hson[u]]+1;
    }
    else{
        d[u][0]=1;
        ans[u]=0;
        return;
    }
    d[u][0]=1;
    if(1>d[u][ans[u]]) ans[u]=0;
    else if(1==d[u][ans[u]]&&0<ans[u]) ans[u]=0;
    for(int i=hd[u];i;i=edge[i].nxt){
        v=edge[i].to;
        if(v!=fa[u]&&v!=hson[u]){
            d[v]=p;
            p+=len[v]<<1;
            dfs2(v);
            for(int j=1;j<=len[v];j++){
                d[u][j]+=d[v][j-1];
                if(d[u][j]>d[u][ans[u]]) ans[u]=j;
                else if(d[u][j]==d[u][ans[u]]&&j<ans[u]) ans[u]=j;
            }
        }
    }
    return;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<n;i++){
        cin>>u>>v;
        add(u,v);
    }
    dfs1(1,0);
    p=null;
    d[1]=p;
    p+=len[1]<<1;
    dfs2(1);
    for(int i=1;i<=n;i++) cout<<ans[i]<<'\n';
    return 0;
}

通过本题可以发现，长链剖分可以用于优化复杂度和树高有关的 DP 问题。

例题3

P5904 [POI 2014] HOT-Hotels 加强版

给定一颗树，设 $dist_{i,j}$ 表示 $i,j$ 之间的距离，求有多少个无序三元组 $(i,j,k)$ 满足 $dist_{i,j}=dist_{j,k}=dist_{k,i}$ 。

设 $1$ 是根， $m$ 表示最深深度，考虑朴素 DP。设 $f_{u,i}$ 表示在 $u$ 子树内的点 $v$ 中满足 $dist_{u,v}=i$ 的点 $v$ 数量， $g_{u,i}$ 表示在 $u$ 子树内的点 $x,y$ 中满足 $dist_{\operatorname{LCA}(x,y),x}=dist_{\operatorname{LCA}(x,y),y}=dist_{\operatorname{LCA}(x,y),u}+i$ 的无序对 $(x,y)$ 数量。

假设现在搜索到了点 $u$ ，正在处理 $u$ 的儿子 $v$ ，可以得到：

$ans:=ans+\sum_{i} f_{u,i}g_{v,i+1}+\sum_{i}f_{v,i-1}g_{u,i} \\ g_{u,i}:=g_{u,i}+g_{v,i+1}+f_{u,i}f_{v,i-1} \\ f_{u,i}:=f_{u,i}+f_{v,i-1}$

边界条件：

$f_{u,0}=1 \\$

这样就是 $O(nm)$ 的复杂度。考虑长链剖分，对于重儿子 $h$ ，我们让 $f_h$ 直接写到 $f_u+1$ 上， $g_h$ 写到 $g_u-1$ 上；对于轻儿子 $v$ ，直接暴力转移。

代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005;
struct graph{
    int nxt,to;
    graph(const int &A=0,const int &B=0):nxt(A),to(B){}
};
int n,u,v,now,tot=1;
long long ans,*p;
int hd[MAXN],dep[MAXN],fa[MAXN],maxd[MAXN],hson[MAXN],len[MAXN];
bool istp[MAXN];
long long null[MAXN<<2],*f[MAXN],*g[MAXN];
graph edge[MAXN<<1];
void add(const int &u,const int &v){
    edge[++tot]=graph(hd[u],v);
    hd[u]=tot;
    edge[++tot]=graph(hd[v],u);
    hd[v]=tot;
    return;
}
void dfs1(const int &u,const int &fath){
    int v;
    fa[u]=fath;
    maxd[u]=dep[u]=dep[fath]+1;
    for(int i=hd[u];i;i=edge[i].nxt){
        v=edge[i].to;
        if(v!=fath){
            dfs1(v,u);
            maxd[u]=max(maxd[v],maxd[u]);
            if(maxd[v]>maxd[hson[u]]) hson[u]=v;
        }
    }
    len[u]=maxd[u]-dep[u]+1;
    return;
}
void dfs2(const int &u){
    int v;
    if(hson[u]){
        f[hson[u]]=f[u]+1;
        g[hson[u]]=g[u]-1;
        dfs2(hson[u]);
    }
    f[u][0]=1;
    ans+=g[u][0];
    for(int i=hd[u];i;i=edge[i].nxt){
        v=edge[i].to;
        if(v!=fa[u]&&v!=hson[u]){
            f[v]=p;
            p+=len[v]<<1;
            g[v]=p;
            p+=len[v]<<1;
            dfs2(v);
            for(int j=0;j<len[v];j++){
                ans+=f[v][j]*g[u][j+1];
                if(j) ans+=f[u][j-1]*g[v][j];
            }
            for(int j=0;j<len[v];j++) g[u][j]+=g[v][j+1];
            for(int j=1;j<=len[v];j++) g[u][j]+=f[u][j]*f[v][j-1];
            for(int j=1;j<=len[v];j++) f[u][j]+=f[v][j-1];
        }
    }
    return;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<n;i++){
        cin>>u>>v;
        add(u,v);
    }
    dfs1(1,0);
    p=null;
    f[1]=p;
    p+=len[1]<<1;
    g[1]=p;
    p+=len[1]<<1;
    dfs2(1);
    cout<<ans;
    return 0;
}