这篇文章笔者想总结一下LCA的做法
LCA即最近公共祖先它所要求的是树上任意两个结点的公共祖先 下面提供做法
1、暴力法：
即一层一层往上爬，给定两个结点，先将两个结点的深度调为一致后，一起一层层的向上爬上升，这种做法的时间复杂度为较大，很容易被卡掉，这里就不详细说明，只是放出代码
#include<iostream>
#include<cstdio> #include<algorithm> #include<cstring> #define ll long long #define maxn 500005 using namespace std; int n,m,s,tot; int head[maxn],deep[maxn],f[maxn],vis[maxn]; struct node { int next,to; } map[maxn*2];//因为是无向图，记得开二倍 void add (int from, int to) { map[tot].next = head[from]; map[tot].to = to; head[from] = tot++; }//存图 void build(int root,int depth) { deep[root] = depth; vis[root] = 1; for(int i=head[root] ;i!=-1;i=map[i].next) { if(vis[map[i].to]) continue; f[map[i].to] = root; build(map[i].to,depth+1); } }//建树，也就是一个dfs的过程，要存储深度 int LCA(int s1,int s2) { while(deep[s1]>deep[s2]) s1 = f[s1]; while(deep[s1]<deep[s2]) s2 = f[s2];//先调到同一深度 while(s1!=s2) { s1 = f[s1]; s2 = f[s2]; }//向上爬 return s1; } int main() { cin>>n>>m>>s; int a,b; memset(head,-1,sizeof(head)); for(int i=1; i<=n-1; i++) { cin>>a>>b; add(a,b); add(b,a); } build(s,1); int son1,son2; for(int i=1 ; i<=m; i++) { cin>>son1>>son2; cout<<LCA(son1,son2)<<endl; }return 0; }
2、现在来说一说一种普遍做法，树上倍增法
在看这里之前，请先保证你对ST表或者RMQ问题有过一定的了解，否则直接看树上倍增会有些难
具体思路和写一个ST表的思路是一样的，只不过这里用fa[i][j]表示第i个结点向上2^j的父亲是谁，即fa[i][0]表示i的父亲,fa[i][1]表示i的爷爷以此类推
相比于暴力做法，我们在dfs建树的过程中又多了一步记录每个点向上2^j的父亲因为考虑到这里要用log2进行处理，我们不妨直接先处理lg数组(即log2(n)是多少)
lg[1]=0; for(int i = 2; i <= n; ++i) lg[i] = lg[i>>1]+1;
当然为了方便使用我们还有一种处理方法
for(int i = 1; i <= n; ++i) lg[i] = lg[i-1] + (1 << lg[i-1] == i)
这样处理的结果就是我们可以直接得到log2(x)+1的值
当然你也可以使用cmath里的log函数，但是这里的log函数并非是log2哦，要记得换底
为了便于理解，我们在后面的代码使用第一种处理方式
给出代码：
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; int n,m,s; struct edge { int next,to; }mp[2*500000]; int cnt; int head[500001],fa[500001][20],deep[500001]; int lg[500001]; void add(int x,int y) { cnt++; mp[cnt].next = head[x]; mp[cnt].to = y; head[x] = cnt; } void build(int root,int father) { deep[root] = deep[father]+1; fa[root][0] = father; for(int i=1; i<=lg[deep[root]]+1; i++) {//log+1 +1is necessary! fa[root][i] = fa[fa[root][i-1]][i-1]; //important 最重要的一步，相当于ST表中的转移方程 } for(int i=head[root]; ~i; i=mp[i].next) { if(mp[i].to!=father) { build(mp[i].to,root); } } return ; } int RMQLCA(int x,int y) { if(deep[x]<deep[y]) swap(x,y); while(deep[x]>deep[y]) x = fa[x][lg[deep[x]-deep[y]+1]-1]; if(x==y) return x; for(int i=lg[deep[x]]+1-1; i>=0; i--) {//log+1 +1 is necseeary 画图 如果不加，则有的点的祖先会算不到，多加没什么影响，因为仅有f[s][0]=0; if(fa[x][i]!=fa[y][i]) { x = fa[x][i]; y = fa[y][i]; } } return fa[x][0]; } int main() { int x,y; scanf("%d%d%d",&n,&m,&s); memset(head,-1,sizeof(head)); for(int i=1; i<=n-1; i++) { scanf("%d%d",&x,&y); add(x,y); add(y,x); } lg[1]=0; for(int i = 2; i <= n; ++i) lg[i] = lg[i>>1]+1; // for(int i = 1; i <= n; ++i) // lg[i] = lg[i-1] + (1 << lg[i-1] == i) // 也可以直接这样处理为log(x)+1 后面调用就不用+1 build(s,0); while(m--) { scanf("%d%d",&x,&y); printf("%d ",RMQLCA(x,y)); } return 0; }
3、其实求LCA还有一种不常用的方法
Tarjan求LCA
先给出代码：
#include<bits/stdc++.h> using namespace std; template<typename Type>inline void read(Type &xx) { Type f=1;char ch;xx=0; for(ch=getchar();ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1; for(;ch>='0'&&ch<='9';ch=getchar())xx=xx*10+ch-'0'; xx*=f; } struct edge { int to,next; }e[1000001];//边的储存 struct questions { int to,next,same,num; bool flag; questions(){flag=false;} }q[1000001];//询问的储存，flag=false表示还没回答，num表示是第几个询问，same储存与这个询问相同的询问序号。 bool b[500001]; int head[500001],que[500001],father[500001]; int n,m,s,nume=0,numq=0,ans[500001]; void add_edge(int x,int y) { e[++nume].to=y; e[nume].next=head[x]; head[x]=nume; e[++nume].to=x; e[nume].next=head[y]; head[y]=nume; } void add_que(int x,int y,int k) { q[++numq].to=y; q[numq].same=numq+1; q[numq].next=que[x]; q[numq].num=k; que[x]=numq; q[++numq].to=x;//询问要储存到两个点的链表序列里，删的时候也要一起删 q[numq].same=numq-1; q[numq].next=que[y]; q[numq].num=k; que[y]=numq; } int find(int x)//并查集 { if(father[x]!=x)father[x]=find(father[x]); return father[x]; } void unionn(int x,int y)//并查集 { father[find(y)]=find(x); } void LCA(int point,int f)//point是当前搜索节点，f是它的父亲 { for(int i=head[point];i!=0;i=e[i].next)//遍历与point相连的所有边 if(e[i].to!=f&&!b[e[i].to]) { LCA(e[i].to,point); unionn(point,e[i].to);//合并 b[e[i].to]=1; } for(int i=que[point];i!=0;i=q[i].next)//遍历与point相关的询问 if(!q[i].flag&&b[q[i].to])//如果另一个点遍历过了并且该询问没有回答过 { ans[q[i].num]=find(q[i].to);//记录下答案 q[i].flag=1; q[q[i].same].flag=1;//把两个点上的询问都去掉 } } int main() { read(n);read(m);read(s); for(int i=1,x,y;i<=n-1;i++) { father[i]=i; read(x);read(y); add_edge(x,y); } father[n]=n; for(int i=1,x,y;i<=m;i++) { read(x);read(y); add_que(x,y,i); } LCA(s,0); for(int i=1;i<=m;i++) printf("%d ",ans[i]); return 0; }
具体讲解可看这里