树上倍增求LCA及例题

先瞎扯几句

树上倍增的经典应用是求两个节点的LCA

当然它的作用不仅限于求LCA,还可以维护节点的很多信息

求LCA的方法除了倍增之外,还有树链剖分、离线tarjan ,这两种日后再讲(众人:其实是你不会吧:unamused:。。。)

思想

树上倍增嘛,顾名思义就是倍增

相信倍增大家都不默认,著名的rmq问题的O(n*logn)的解法就是利用倍增实现的

在树上倍增中,我们用

f[j][i]表示第j号节点,跳了2^j步所能到达的节点

deep[i]表示i号节点的深度

然后用这两个数组瞎搞搞就能整出LCA来啦

众人::wrench:  :hammer: :hocho:

实现

deep&&f[i][0]

首先,f[i][0](也就是一个节点的上面的节点)容易求得,只要对整棵树进行一边dfs就好,在dfs的时候我们顺便可以求出deep数组

for(int i=head[now];i!=-1;i=edge[i].nxt)
        if(!deep[edge[i].v])
            deep[edge[i].v]=deep[now]+1,f[edge[i].v][0]=now,dfs(edge[i].v);

这段代码应该不难理解

f[j][i]

那么我们怎么维护f数组呢?

不难得到f[j][i]=f[f[j][i-1]][i-1] 众人:难!

其实真的不难,一张图就可以解释明白啦

这句话的意思其实是说,一个节点跳$2^j$所能到达的节点实际上是跳2^{i-1}所能到达的节点再往上跳2^{j-1}

注意2^i=2^{i-1}+2^{i-1}

代码:

for(int i=1;i<=19;i++)	
    for(int j=1;j<=n;j++)
        f[j][i]=f[f[j][i-1]][i-1];

LCA

接下来要进入最核心的部分啦,

我们如何用deep和f乱搞搞出x和y的LCA呢?

按照书上倍增算法的介绍

我们求LCA需要分为两步

deep[x]>deep[y]

  1. 让x向上跳,跳到与y深度相同位置
  2. 让x和y同时向上跳,跳到祖先相同位置

根据二进制分解什么乱七八糟的,这么做一定是对的,其实这个挺显然的,yy一下就好了吧。。。

第一步

if(deep[x]<deep[y])	swap(x,y);
	for(int i=19;i>=0;i--)
  	  if(deep[f[x][i]]>=deep[y])
     	   x=f[x][i];

首先处理一下x和y的深度,保证deep[x]>deep[y]

然后尽量让x向上跳就好啦,注意这里是可以取到等号的

注意这里可能会出现一种特殊情况

这个时候他们的最近公共祖先就是y

if(x==y)	return x;

 第二步

同时向上跳,直到祖先相同为止

那么此时他们再向上跳一步所能到达的节点就是LCA啦

for(int i=19;i>=0;i--)
    if(f[x][i]!=f[y][i])
        x=f[x][i],y=f[y][i];
return	f[x][0];

怎么样?

是不是很简单?

完整代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=1000010;
inline void read(int &n)
{
    char c=getchar();bool flag=0;n=0;
    while(c<'0'||c>'9')	c=='-'?flag=1,c=getchar():c=getchar();
    while(c>='0'&&c<='9')	n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;
}
struct node
{
    int v,nxt;
}edge[MAXN];
int head[MAXN];
int num=1;
inline void add_edge(int x,int y)
{
    edge[num].v=y;
    edge[num].nxt=head[x];
    head[x]=num++;
}
int f[MAXN][21];
int deep[MAXN];
int n,m,root;
void dfs(int now)
{
    for(int i=head[now];i!=-1;i=edge[i].nxt)
        if(!deep[edge[i].v])
            deep[edge[i].v]=deep[now]+1,f[edge[i].v][0]=now,dfs(edge[i].v);
}
void PRE()
{
    for(int i=1;i<=19;i++)	
        for(int j=1;j<=n;j++)
            f[j][i]=f[f[j][i-1]][i-1];
} 
int LCA(int x,int y)
{
    if(deep[x]<deep[y])	swap(x,y);
    for(int i=19;i>=0;i--)
        if(deep[f[x][i]]>=deep[y])
            x=f[x][i];
    if(x==y)	return x;
    for(int i=19;i>=0;i--)
        if(f[x][i]!=f[y][i])
            x=f[x][i],y=f[y][i];
    return	f[x][0];
}
int main()
{
    
    memset(head,-1,sizeof(head));
    read(n);read(m);read(root);
    for(int i=1;i<=n-1;i++)
    {
        int x,y;read(x);read(y);
        add_edge(x,y);
        add_edge(y,x);
    }
    deep[root]=1;
    dfs(root);
    PRE();
    for(int i=1;i<=m;i++)
    {
        int x,y;
        read(x);read(y);
        printf("%d\n",LCA(x,y));
    }
    return 0;
} 

例题

都是些入门难度的题目

洛谷P3379 【模板】最近公共祖先(LCA)

POJ 1986 Distance Queries

http://www.cnblogs.com/zwfymqz/p/7791527.html

HDU 3078 Network

http://www.cnblogs.com/zwfymqz/p/7791617.html

HDU 2586 How far away ?

http://www.cnblogs.com/zwfymqz/p/7791517.html

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏FreeBuf

SQL注入之骚姿势小记

写在前面 小记一下CTF那些日子和DROPS队友学到的SQL注入的骚姿势。 By 010 1、IN之骚 这个我也偶然发现的,也不知前辈们有没有早已总结好的套路了...

41560
来自专栏机器学习算法与Python学习

PyTorch 的这些更新,你都知道吗?

3.7K40
来自专栏点滴积累

geotrellis使用(十四)导出定制的GeoTiff

Geotrellis系列文章链接地址http://www.cnblogs.com/shoufengwei/p/5619419.html 目录 前言 需求说...

32560
来自专栏信安之路

栈溢出利用之Return to dl-resolve

在CTF中一般的栈溢出题目会给出程序对应的libc,这样我们在泄漏一个libc地址之后就能根据偏移量去计算libc的其他地址,比如system、/bin/sh或...

10000
来自专栏AI科技大本营的专栏

PyTorch 重磅更新,不只是支持 Windows

这次版本的主要更新一些性能的优化,包括权衡内存计算,提供 Windows 支持,24个基础分布,变量及数据类型,零维张量,张量变量合并,支持 CuDNN 7.1...

30520
来自专栏YG小书屋

ES 查询优化(二)

1.4K30
来自专栏人工智能头条

TensorFlow架构与设计:OP本质论

26840
来自专栏落影的专栏

使用VideoToolbox硬编码H.264

前言 H.264是目前很流行的编码层视频压缩格式,目前项目中的协议层有rtmp与http,但是视频的编码层都是使用的H.264。 在熟悉H.264的过程中,为...

48480
来自专栏小小挖掘机

数据城堡参赛代码实战篇(四)---使用pandas合并数据表

小编们最近参加了数据城堡举办的“大学生助学金精准资助预测”比赛,分组第19名的成绩进入了复赛,很激动有木有!在上一篇文章中,小编主要介绍了pandas中使用dr...

42260
来自专栏牛肉圆粉不加葱

揭开Spark Streaming神秘面纱④ - job 的提交与执行

前文揭开Spark Streaming神秘面纱③ - 动态生成 job 我们分析了 JobScheduler 是如何动态为每个 batch生成 jobs,本文...

8130

扫码关注云+社区

领取腾讯云代金券