AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

树链剖分详讲(重链剖分+长链剖分)

作者: 作者的头像   銘权 ,  2019-07-20 10:17:48 ,  所有人可见 ,  阅读 1972


14


13

关于树链剖分(重链剖分+长链剖分)

重链剖分:

·重儿子:每个点的子树中,子树的节点数和最大的子节点
·轻儿子:除重儿子外的其他子节点
·重边:每个节点与其重儿子间的边
·轻边:每个节点与其轻儿子间的边
·重链:重边连成的链 (一个点也可以看作是重链)
·轻链:轻边连成的链

如下图:

重链剖分.png

很明显,一棵树可以被剖分成若干个无交集的重链,而剖分的过程就叫做重链剖分

重链剖分的实现:

两次 dfs
第一次 dfs:处理出每个点的重儿子,子树的节点数和,深度,父节点
关于重儿子,子树节点数和处理的实现:先深搜,在回溯时记录
第二次 dfs:处理出每个点所在重链的链头
深搜时,如果搜到重儿子,链头不变;搜到轻儿子,链头改成轻儿子就行了

代码实现:


const int N=500000+10;

int wson[N],  size[N],     fa[N],  dep[N],  top[N];
//  重儿子  子树节点数和  父节点  节点深度   链头 
int head[N],ver[N*2],nex[N*2];

void dfs1(int x)
{
    size[x]=1;
    dep[x]=dep[fa[x]]+1;
    for(int i=head[x];i;i=nex[i])
    {
        int y=ver[i];
        if(y!=fa[x])
        {
            fa[y]=x;
            dfs1(y);
            size[x]+=size[y];
            if(size[y]>size[wson[x]]) wson[x]=y;
            //回溯时更新子树节点和、重儿子
        }
    }
}

void dfs2(int x,int nowtop)
{
    top[x]=nowtop;
    if(wson[x]) dfs2(wson[x],nowtop);
    //重儿子链头不变 
    for(int i=head[x];i;i=nex[i])
    {
        int y=ver[i];
        if(y!=fa[x]&&y!=wson[x]) dfs2(y,y);
        //轻儿子代表一条新的重链,链头为轻儿子 
    }
}

重链剖分的一些性质:

·所有重链互不相交,每个点只属于一条重链
·所有重链长度和等于节点数
·一个点到根节点的路径上经过的边中轻边最多只有 log 条(重儿子和轻儿子节点数和相等时取到)

重链剖分的用处:

·O(1) 移动到链头 (求 lca)
·直接修改或查询重链上的信息 (结合线段树)

重链剖分求 lca 的实现步骤:

1) 将两点中链头更深的点跳到链头
2) 若两点不在同一重链上,更深点跳转到父节点
3) 重复操作 1)、2)直到两点处于同一条重链上,此时深度较浅的点即为所求

关于 3) 的证明:

很明显当两点处于同一条重链上时,它们的父节点也处于这条重链上,并且这个父节点,就是这两点中深度较浅的点。

代码实现:

#include<bits/stdc++.h>
using namespace std;

const int N=500000+10;

int wson[N],size[N],fa[N],dep[N],top[N];
int head[N],ver[N*2],nex[N*2];
int n,m,tot=0,root=1;           //一般根节点为 1  

void add(int x,int y)
{
    ver[++tot]=y;
    nex[tot]=head[x];
    head[x]=tot;
}

void dfs1(int x)
{
    size[x]=1;
    dep[x]=dep[fa[x]]+1;
    for(int i=head[x];i;i=nex[i])
    {
        int y=ver[i];
        if(y!=fa[x])
        {
            fa[y]=x;
            dfs1(y);
            size[x]+=size[y];
            if(size[y]>size[wson[x]]) wson[x]=y;
        }
    }
}

void dfs2(int x,int nowtop)
{
    top[x]=nowtop;
    if(wson[x]) dfs2(wson[x],nowtop);
    for(int i=head[x];i;i=nex[i])
    {
        int y=ver[i];
        if(y!=fa[x]&&y!=wson[x]) dfs2(y,y);
    }
}

int lca(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        x=fa[top[x]];
        //将所在链的链头更深的点跳到链头 
    }
    return dep[x]<dep[y]?x:y;
    //返回深度更浅的点 
}

int main()
{
    scanf("%d%d%d",&n,&m,&root);
    //scanf("%d%d",&n,&m);
    for(int i=1,x,y;i<n;++i)
    {
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }

    dfs1(root);
    dfs2(root,root);
    //根节点为最长长链的链头

    for(int i=1,x,y;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        printf("%d\n",lca(x,y));
    }

    return 0;
}

长链剖分:

·长儿子:子树深度最大的子节点
·短儿子:除长儿子外的子节点
·长边:每个节点与长儿子间的连边
·短边:每个节点与短儿子间的连边
·长链:长边构成的链
·短链:短边构成的链

如下图:

长链剖分.png

与重链剖分一样,一棵树被分成若干个无交集的长链,叫长链剖分

长链剖分的实现:与重链剖分类似,也是两次 dfs

代码实现:


const int N=500000+10;

int lson[N],maxlen[N], fa[N],   dep[N], top[N];
//  长儿子  子树深度  父节点  节点深度  链头 
int head[N],ver[N*2],nex[N*2];

void dfs1(int x)
{
    dep[x]=dep[fa[x]]+1;
    maxlen[x]=dep[x];
    for(int i=head[x];i;i=nex[i])
    {
        int y=ver[i];
        if(y!=fa[x])
        {
            fa[y]=x;
            dfs1(y);
            maxlen[x]=max(maxlen[y],maxlen[x]);
            if(maxlen[y]>maxlen[lson[x]]) lson[x]=y;
            //回溯时更新子树深度和长儿子 
        }
    }
}

void dfs2(int x,int nowtop)
{
    top[x]=nowtop;
    if(lson[x]) dfs2(lson[x],nowtop);
    //长儿子链头不变 
    for(int i=head[x];i;i=nex[i])
    {
        int y=ver[i];
        if(y!=fa[x]&&y!=lson[x]) dfs2(y,y);
        //短儿子代表一条新的长链,链头为短儿子 
    }
}

长链剖分的性质:

长链剖分有比重链剖分更好的性质
·任意点祖先所在长链长度一点大于等于这个点所在长链长度
·所有长链长度之和就是总结点数
·一个点到根节点的路径上经过的短边最多有 √n 条 (长儿子深度和短儿子深度相等时取到)

长链剖分的用处:

·O(1) 移动到链头 (求lca,和重链剖分一样)
·O(nlogn) 预处理,单次 O(1) 在线查询一个点的 k 级祖先
·O(n) 处理可合并的与深度有关的子树信息 (例如某深度点数、某深度点权和)

长链剖分求 lca 的代码实现:

#include<bits/stdc++.h>
using namespace std;

const int N=500000+10;

int lson[N],maxlen[N],fa[N],dep[N],top[N]; 
int head[N],ver[N*2],nex[N*2];
int n,m,tot=0,root=1;

void add(int x,int y)
{
    ver[++tot]=y;
    nex[tot]=head[x];
    head[x]=tot;
}

void dfs1(int x)
{
    dep[x]=dep[fa[x]]+1;
    maxlen[x]=dep[x];
    for(int i=head[x];i;i=nex[i])
    {
        int y=ver[i];
        if(y!=fa[x])
        {
            fa[y]=x;
            dfs1(y);
            maxlen[x]=max(maxlen[y],maxlen[x]);
            if(maxlen[y]>maxlen[lson[x]]) lson[x]=y;
        }
    }
}

void dfs2(int x,int nowtop)
{
    top[x]=nowtop;
    if(lson[x]) dfs2(lson[x],nowtop);
    for(int i=head[x];i;i=nex[i])
    {
        int y=ver[i];
        if(y!=fa[x]&&y!=lson[x]) dfs2(y,y);
    }
}

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

int main()
{
    scanf("%d%d%d",&n,&m,&root);
    //scanf("%d%d",&n,&m);
    for(int i=1,x,y;i<n;++i)
    {
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }

    dfs1(root);
    dfs2(root,root);

    for(int i=1,x,y;i<=m;++i)
    {
        scanf("%d%d",&x,&y);
        printf("%d\n",lca(x,y));
    }

    return 0;
}

关于在线求 k 级祖先的实现:

1) 暴力预处理出每个链头往上链长个祖先及这条链上所有的点,再预处理出所有二进制的最高次幂
2) 查询祖先时,先跳能跳的 2 的最高次幂,再在所在链的链头上 O(1) 查询祖先

关于 2) 的证明:

我们由长链的性质得,点 x 往上跳 k/2 个点到达的长链深度一点大于 k/2 ,也就是链的长度一定大于 k/2
所以无论 x 的 k 级祖先在原先链上
还是在点 x 的 2 的最高次幂祖先所在的链上
还是在点 x 的 2 的最高次幂祖先所在的链的链头上方
都在我们预处理的范围内,就都能做到 O(1) 求出祖先了

代码实现:

#include<bits/stdc++.h>
using namespace std;

const int N=500000+10;

int lson[N],maxlen[N],fa[N],dep[N],top[N]; 
int head[N],ver[N*2],nex[N*2];
int f[N][22],st[N*2];
vector<int> up[N],down[N];
int n,m,tot=0,root=1;

void add(int x,int y)
{
    ver[++tot]=y;
    nex[tot]=head[x];
    head[x]=tot;
}

void dfs1(int x)
{
    dep[x]=dep[fa[x]]+1;
    maxlen[x]=dep[x];
    f[x][0]=fa[x];
    for(int i=1;i<=19;i++)
    {
        if(f[x][i-1]) f[x][i]=f[f[x][i-1]][i-1];
        else break;
    }
    for(int i=head[x];i;i=nex[i])
    {
        int y=ver[i];
        if(y!=fa[x])
        {
            fa[y]=x;
            dfs1(y);
            maxlen[x]=max(maxlen[y],maxlen[x]);
            if(maxlen[y]>maxlen[lson[x]]) lson[x]=y,maxlen[x]=maxlen[y];
        }
    }
}

void dfs2(int x,int nowtop)
{
    top[x]=nowtop;
    if(lson[x]) dfs2(lson[x],nowtop);
    for(int i=head[x];i;i=nex[i])
    {
        int y=ver[i];
        if(y!=fa[x]&&y!=lson[x]) dfs2(y,y);
    }
}

void chain_prework(int x)       //预处理 
{
    int rot=x,len=maxlen[x]-dep[x];
    //rot 为链头,len 为链长 
    x=fa[rot];
    while(dep[rot]-dep[x]<=len&&x)
    {
        up[rot].push_back(x);
        x=fa[x];
        //处理链头上方链长个点 
    }
    x=rot;
    while(lson[x])
    {
        down[rot].push_back(lson[x]);
        x=lson[x];
        //处理链中的点 
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1,x,y;i<n;++i)
    {
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }

    dfs1(root);
    dfs2(root,root);

    st[1]=0;
    for(int i=2;i<=n;++i) st[i]=st[i>>1]+1;
    for(int i=1;i<=n;++i) 
        if(i==top[i]) chain_prework(i);

    for(int i=1,x,y;i<=m;++i)
    {
        int ans=0; 
        scanf("%d%d",&x,&y);
        x=x^ans;
        y=y^ans;
        if(y==0) ans=x;
        else if(y>=dep[x]) ans=0;
        else
        {
            x=f[x][st[y]];
            y-=(1<<st[y]);
            //先跳能跳的 2 的最大次幂
            if(y==0) ans=x;
            else if(y<dep[x]-dep[top[x]]) ans=down[top[x]][dep[x]-dep[top[x]]-y-1];
            //在链中 
            else if(y==dep[x]-dep[top[x]]) ans=top[x];
            //在链头 
            else ans=up[top[x]][y-dep[x]+dep[top[x]]-1];
            //在链上方 
        }
        printf("%d\n",ans);
    }

    return 0;
}

不要忘记收藏防迷路吖 (`・ω・´)

4 评论


用户头像
秦淮岸灯火阑珊   2019-07-20 14:07      1    踩      回复

👍

用户头像
銘权   2019-07-20 14:20         踩      回复

谢( ̄▽ ̄)~


用户头像
yxc   2019-07-20 11:02      1    踩      回复

赞!

用户头像
銘权   2019-07-20 11:03         踩      回复

谢( ̄▽ ̄)


App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息