LCA

$\texttt{LCA算法By Billy2007}$

1. 前言

   众所周知Billy2007树论不行，为了记住求LCA的方法，于是开了这个天坑。

   LCA（Least Common Ancestors），即最近公共祖先，是指在有根树中，找出某两个结点u和v最近的公共祖先。

   为了方便，我们这里定义：

   const int N=500001;
   

   感谢@夏夜空 的题解！

2. 怎么求LCA

   以P3379为例。

   2.1 暴力

   暴力算法：让这两个点像并查集一样暴力搜索，直到第一次相遇为止。

   struct node{
       int bianh;
       int fa,chd[N/1000];//考虑乐观情况
       node(){
           fa=0;
           bianh=0;
           memset(chd,0,sizeof(chd));
           //这里3个都要定为0.
       }
   };
   int lca(int a,int b){
       if(a==b) return a;
       return lca(nd[a].fa,nd[b].fa);
   }
   

   但是这个算法有问题。

   显然我们不知道是 $a$是$b$的父亲还是$b$是$a$的父亲。

   这个可以通过dfs解决，具体代码在后面。

   并且空间只考虑乐观情况，可能到时候会出现$1$是根，而$2$到$N$都是兄弟的情况。

   这样会造成空间的大量浪费。

   并且就算可行，初始化dfs时间复杂度$O(n)$，每一次最坏时间复杂度$O(n)$，总时间复杂度$O(nm)$，肯定会被T飞（废话）。

   ---

   2.2 倍增

   我们可以使用倍增算法——一种通过抄题解记录$a$的前$2^i$代来达到$O(\log n)$求LCA的算法。

   我们假设有一棵$n$点$m$边的多叉树。

   一个一个点存显然不现实，那咋办？

   • 可以把静态的数组转换成vector，更为方便。
   • 从存每一个点的父亲变成存每一个点往上数的第$2^k(k\le 22)$个祖先。

   转换后，一棵树的定义如下：

   vector<int> sons[N];//sons[i][j]表示i的第j个儿子。
   int dep[N],lga[N],n,m,s,fa[N][22];//这里dep[i]表示第i个点的深度，lga[i]表示lb(i)+1。n,m,s同题目要求。
   

   注：$lb(i)=log_2^i$。

   这里$fa_{i,j}$表示$i$往上数的第$2^j$个祖先。因为$2^{22}=4194304$，远远大于$N$。

   可能有人会问了：为什么这里$fa_{i,j}$存 $i$往上数的第$2^j$个祖先，而不存 $i$往上数的第$j$个祖先？

   原因如下：

   • $O(N\times N)$的空间复杂度显然$\color{darkblue}MLE$；
   • 每次遇到一个点都要往上爬看他的祖先，时间复杂度巨大。如果这棵树是一条链，那么遍历这棵树的时间复杂度是$O(\sum_{i=0}^{n-1}i)=O(\frac{n(n-1)}{2})=O(n^2)$。（注：这里我也不知道为啥）

3. 倍增的实现

   显然我们这里需要先做一个连接的函数。

   void add(int s,int t){
   	sons[s].push_back(t);
   }
   

   接下来，我们写一个求$lb(i)$的函数。

   void init(int to){
       for(int i=1;i<=to;i++){
           lga[i]=lga[i-1];
           if(i==1<<lga[i-1]) lga[i]++;
       }
   }
   

   接下来，还是那个老问题。

   所以，我们需要一个dfs函数。

   void dfs(int now,int fanow){//参数fanow就是now他爸
       dep[now]=dep[fanow]+1;//记录深度
       fa[now][0]=fanow;
       for(int i=1;(1<<i)<=dep[now];i++){
           //记录祖先
           fa[now][i]=fa[fa[now][i-1]][i-1];
       }
       for(int i=0;i<sons[now].size();i++){//注意，这里是vector
           if(sons[now][i]!=fanow){//我们在加边是因为还没有dfs，所以把父亲也加入了sons
           	dfs(sons[now][i],now);
           }
       }
   }
   

   在记录祖先的过程中，这里$i$对应第$2^i$层，$now$往上第$2^i$祖先就是$now$往上第$2^{i-1}$个祖先的第$2^{i-1}$个祖先。

   比如下面的树。

           1
          /  \
        2     3
      /  \   
    4    5
   

   （画的比较丑，不要喷）

   显然$2$的第$2^0$个祖先是$1$，那么$5$的第$2^1$个祖先就是$5$的第$2^0$个祖先的第$2^0$个祖先。

   哇哇哇，递归！

   形成了递归关系后，那么接下来就好做多了。

4. 题外话

   是不是所有 实数$a$ 都可以用$\sum_{i=0}^n 2^i\times k_i(k_i\in \{0,1\})$表示呢？

   答案是对。

   显然任何一个实数$a$ 都可以表示成二进制表示，那么二进制就是上式的形式。

5. 最核心的部分

   假设$b(x)=2^x$。

   int lca(int x,int y){
   	if(dep[x]<dep[y]) swap(x,y);//这里为了方便，让x永远比y深
   	while(dep[x]>dep[y]) x=fa[x][lga[dep[x]-dep[y]]-1];
   	//这里的lga是lb(dep[x]-dep[y]+1)，所以还要-1。
   	//这里就是直接让x跳到和y同一深度，再接下去搞。
   	//个人不明白为什么还要写个while。
   	//现在懂了，可能需要跳很多次（比如8->4->1）才可以到。
   	if(x==y) return x;
   	//如果一跳，得，直接一样了，那么lca就是x了（写y也可以/cy）
   	for(int i=lga[x];i>=0;i--){
   		if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
   		/*
   		全场最NB代码
   		如果现在两个节点的b(x)层父亲相等，那么说明步子跨大了。
   		那么就不要跨了。
   		否则，就说明现在还需要跨。
   		那么就继续给我跨。
   		如果现在两个点已经到了合并态（注：比如上面那棵树的2和3,4和5），那么就不要管他了。
   		jojo！时间复杂度O(lb(n))!
   		*/
   	}
   	return fa[x][0];//这里x他爸就是lca，因为现在x和y已经到了合并态。
   }
   

6. 完整代码

   #include<bits/stdc++.h>
   #define ns "-1"
   #define fs(i,x,y,z) for(ll i=x;i<=y;i+=z)
   #define ft(i,x,y,z) for(ll i=x;i>=y;i+=z)
   #define ll long long
   #define ull unsigned long long
   #define db double
   #define ms(a,b) memset(a,b,sizeof(a))
   #define sz(a) sizeof(a)
   using namespace std;
   const int N=500001,inf=0x7f7f7f7f;
   vector<int> sons[N];
   int dep[N],lga[N],n,m,s,fa[N][22];
   void add(int s,int t){
       sons[s].push_back(t);
   }
   void init(int to){
   	for(int i=1;i<=to;i++){
   		lga[i]=lga[i-1];
   		if(i==1<<lga[i-1]) lga[i]++;
   	}
   }
   void dfs(int now,int fanow){
   	dep[now]=dep[fanow]+1;
   	fa[now][0]=fanow;
   	for(int i=1;(1<<i)<=dep[now];i++){
   		fa[now][i]=fa[fa[now][i-1]][i-1];
   	}
   	for(int i=0;i<sons[now].size();i++){
       	if(sons[now][i]!=fanow){
        	   dfs(sons[now][i],now);
       	}
   	}
   }
   int lca(int x,int y){
   	if(dep[x]<dep[y]) swap(x,y);
   	while(dep[x]>dep[y]) x=fa[x][lga[dep[x]-dep[y]]-1];
   	if(x==y) return x;
   	for(int i=lga[x];i>=0;i--){
   		if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
   	}
   	return fa[x][0];
   }
   inline int read(){
   	int date=0,w=1;char c=0;
   	while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
   	while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
   	return date*w;
   }
   int main(){
   	n=read();m=read(),s=read();
   	init(n);
   	for(int i=1;i<n;i++){
   		int x,y;x=read(),y=read();
   		add(x,y);
   		add(y,x);
   	}
   	dfs(s,0);
   	for(int i=1;i<=m;i++){
   		int x,y;x=read(),y=read();
   		printf("%d\n",lca(x,y));
   	}
   	return 0;
   }