LCA——树上倍增

首先，什么是LCA？

LCA：最近公共祖先

祖先：从当前点到根节点所经过的点，包括他自己，都是这个点的祖先

A和B的公共祖先：同时是A，B两点的祖先的点

A和B的最近公共祖先：深度最大的A和B的公共祖先

树上倍增：预处理nlog₂n 求解nlog₂n

原理大体描述：两个点都往上找，找到的第一个相同的点，就是他们的LCA

这里会有两个问题：

Q1：若两个点深度不同，可能会错开

Q2：若真一个一个往上找，时间太慢

对于Q1，如果两个点深度不同，而我们又需要它们深度相同，那就想办法让他们深度相同就行了呗，让更深的先跳到和另一个点深度一样，具体看代码

对于Q2，我们就要看标题了，很明显，用倍增可以缩减时间

原理讲得差不多了，是时候说怎么做了，实在不懂，代码有注释QWQ

首先，深搜一遍，目的是处理每个点的深度和f[i][j]，深度用deap[]记录，f[i][j]的含义是i点向上跳2^j个点所到达的点，在此之前，先处理log[i](跳i个点的j是多少，j就是前面提到的2j的j)

代码：

1 for(rll i=1;i<=n;++i)

2     {

3         lg[i]=lg[i-1]+(1<<lg[i-1]==i);//(1<<lg[i-1])先进行，然后判断是否相等

4         //如果相等，就说明(1<<lg[i-1])能跳到这里  lg[i]=log2(i)

5     }

 1 oid dfs(ll u,ll fat)//u 子节点 fat u的父节点

 2 {

 3     f[u][0]=fat;//u向上跳1<<0(=1)个点就是父节点

 4     deap[u]=deap[fat]+1;//深度为父节点+1

 5     for(rll i=1;i<=lg[deap[u]];++i)//更新f数组

 6     {

 7         f[u][i]=f[f[u][i-1]][i-1];//倍增算法

 8     }

 9     for(rll i=head[u];i;i=e[i].nxt)//遍历边

10     {

11         ll v=e[i].v;

12         if(v!=fat)//判断到达的点是否是父节点(毕竟不能绕回去)

13         {

14             dfs(v,u);//继续搜索

15         }

16     }

17 }

然后，比较两点的深度，操作就是让深的跳到浅的，使得两点深度一样

代码：

1 if(deap[u]<deap[v])//保证u的深度比v大

2     {

3         u=u^v,v=u^v,u=u^v;//相当于swap(u,v); ^ 异或符号

4     }

5     while(deap[u]>deap[v])//如果两点深度不同，那就让深度大的点跳到和另一个点的深度

6     {

7         u=f[u][lg[deap[u]-deap[v]]-1];//更新u

8         //为什么-1，个人理解，做事要留有余地

9     }

现在，一样深了，此时如果A和B是同一个点了，那这个点就是他们的LCA，直接返回结束即可

1 if(u==v)    return u;//如果是一个点，直接返回

否则，继续向下进行

两点同时向上跳，如果两点跳后仍不同，继续跳，同时更新值，如果相同，这里不确定该点是否是两点的LCA，因此，不更新值，将距离调小，继续跳(说白了就是不让他们相同)，最后，他们肯定会跳到他们的LCA的孩子上(因为不让他们相等，距离又在不断减小，他们会距离LCA越来越近)，返回当前点的父亲即可

代码：

1 for(rll i=lg[deap[u]]-1;i>=0;i--)//继续向上跳

2     {

3         if(f[u][i]!=f[v][i])//如果他们没碰面

4         {

5             u=f[u][i],v=f[v][i];//更新数值，继续跳

6         }

7     }

8     return f[u][0];//返回

完整代码：

  1 #include<bits/stdc++.h>

  2 #define ll long long

  3 #define rll register long long

  4 using namespace std;

  5 const ll N=5e5+5;

  6 ll n,m,s,cnt;

  7 struct edge

  8 {

  9     ll u,v,nxt;

 10 };

 11 edge e[N<<1];//边表存树

 12 ll head[N],deap[N],f[N][20],lg[N];

 13 //head 记录该点发出的最后一条边 deap 该点的深度

 14 //f[i][j] 第i号点向上跳(1<<j)个点后到达的点 lg 记录log,节约时间

 15 inline ll read()//快读模板

 16 {

 17     ll x=0;

 18     bool flag=false;//判断是否是负数

 19     char ch=getchar();

 20     while(ch<'0'||ch>'9')

 21     {

 22         if(ch=='-') flag=true;

 23         ch=getchar();

 24     }

 25     while(ch>='0'&&ch<='9')

 26     {

 27         x=(x<<3)+(x<<1)+ch-'0';

 28         //(x<<3)左移，相当于x乘8，(x<<1)相当于x乘2，乘法结合律，x乘了10

 29         ch=getchar();

 30     }

 31     if(flag)    return ~(x-1);//是负数，减1取反

 32     return x;//是正数，直接输出

 33 }//快读

 34 void add(ll u,ll v)//建边

 35 {

 36     e[++cnt].u=u;//起始点

 37     e[cnt].v=v;//终点

 38     e[cnt].nxt=head[u];//记录边

 39     head[u]=cnt;//更新最后的边

 40 }

 41 void dfs(ll u,ll fat)//u 子节点 fat u的父节点

 42 {

 43     f[u][0]=fat;//u向上跳1<<0(=1)个点就是父节点

 44     deap[u]=deap[fat]+1;//深度为父节点+1

 45     for(rll i=1;i<=lg[deap[u]];++i)//更新f数组

 46     {

 47         f[u][i]=f[f[u][i-1]][i-1];//倍增算法

 48     }

 49     for(rll i=head[u];i;i=e[i].nxt)//遍历边

 50     {

 51         ll v=e[i].v;

 52         if(v!=fat)//判断到达的点是否是父节点(毕竟不能绕回去)

 53         {

 54             dfs(v,u);//继续搜索

 55         }

 56     }

 57 }//搜索，填f数组

 58 ll lca(ll u,ll v)

 59 {

 60     if(deap[u]<deap[v])//保证u的深度比v大

 61     {

 62         u=u^v,v=u^v,u=u^v;//相当于swap(u,v); ^ 异或符号

 63     }

 64     while(deap[u]>deap[v])//如果两点深度不同，那就让深度大的点跳到和另一个点的深度

 65     {

 66         u=f[u][lg[deap[u]-deap[v]]-1];//更新u

 67         //为什么-1，个人理解，做事要留有余地

 68     }

 69     if(u==v)    return u;//如果是一个点，直接返回

 70     for(rll i=lg[deap[u]]-1;i>=0;i--)//继续向上跳

 71     {

 72         if(f[u][i]!=f[v][i])//如果他们没碰面

 73         {

 74             u=f[u][i],v=f[v][i];//更新数值，继续跳

 75         }

 76     }

 77     return f[u][0];//返回

 78 }//求lca

 79 int main()

 80 {

 81     n=read(),m=read(),s=read();

 82     for(rll i=1;i<n;++i)

 83     {

 84         ll u,v;

 85         u=read(),v=read();

 86         add(u,v);

 87         add(v,u);

 88     }

 89     for(rll i=1;i<=n;++i)

 90     {

 91         lg[i]=lg[i-1]+(1<<lg[i-1]==i);//(1<<lg[i-1])先进行，然后判断是否相等

 92         //如果相等，就说明(1<<lg[i-1])能跳到这里  lg[i]=log2(i)

 93     }

 94     dfs(s,0);

 95     for(rll i=1;i<=m;++i)

 96     {

 97         ll a,b;

 98         a=read(),b=read();

 99         printf("%lld\n",lca(a,b));

100     }

101     return 0;

102 }

巴特西

LCA——树上倍增

最新文章

热门文章