最近公共祖先：在一个有根树中,结点u、v的最近公共祖先是满足是u,v的公共祖先并且深度尽可能大的结点。
1、倍增法
首先如果两个点的深度如果不同，将深度较大的点跳到与深度较小的点一样的深度，再同时向上跳，首次相遇时即为最近公共祖先。
#include<bits/stdc++.h> using namespace std; const int maxn=10000+15; vector<int>vec[maxn];//记录树的边 int n,m,x,y,p,q,t; int dad[maxn][maxn],deep[maxn];//dad i j 为结点i的第2^j个祖先； int lca(int x,int y) { if(deep[x]>deep[y])swap(x,y);//将深度小的结点前置 for(int i=20;i>=0;i--){if(deep[dad[y][i]]>=deep[x])y=dad[y][i];}//滚动到相同的深度 if(x==y)return x; for(int i=20;i>=0;i--){if(dad[x][i]!=dad[y][i]){x=dad[x][i],y=dad[y][i];}}//一起倍增找祖先 return dad[x][0]; } void dfs(int x) { deep[x]=deep[dad[x][0]]+1;//深度为其爸爸的深度＋1 for(int i=0;dad[x][i];i++) dad[x][i+1]=dad[dad[x][i]][i];//滚动赋值，如果结点x的第2^i个祖先存在，那么x的第2^（i+1）个祖先=结点x的第2^i个祖先再往前面2^i个祖先。 for(int i=0;i<vec[x].size();i++) if(!deep[vec[x][i]]){dad[vec[x][i]][0]=x;dfs(vec[x][i]);}//记录爸爸 深搜 } int main() { scanf("%d%d%d",&n,&m,&t);//n个点m条边t个访问； for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); vec[x].push_back(y); vec[y].push_back(x); } dfs(1); while(t--) { scanf("%d%d",&p,&q); printf("%d ",lca(p,q)); } return 0; }
2、树剖法
size x为以x为结点的子树的结点的个数 每个结点和它的儿子之间只有一条重边，这个重边连向它的儿子中size最大的那个儿子。
如果结点u和它的儿子v之间是一条轻边，那么sizev*2<size u，因为这个儿子一定分不到它爸爸size的一半嘛。
top i 记录i结点所在链的链头，如果top u !=top v 说明u v不在一条链上 将 u=dad[u]，重复上述操作；当它们在一条链上时，深度较小的那个点为他们的lca;
#include<bits/stdc++.h> using namespace std; const int maxn=1000+15; vector<int>vec[maxn]; int m,n,x,y,p,q,t; int deep[maxn],size[maxn],dad[maxn],top[maxn]; void dfs(int x) { size[x]=1;deep[x]=deep[dad[x]]+1; for(int i=0;i<vec[x].size();i++) { if(dad[x]!=vec[x][i]) { dad[vec[x][i]]=x; dfs(vec[x][i]); size[x]+=size[vec[x][i]];//加上它儿子的size } } } void dfs1(int x) { int s=0; if(!top[x])top[x]=x;//先让每个链头赋值它本身 for(int i=0;i<vec[x].size();i++) { if(dad[x]!=vec[x][i]&&size[vec[x][i]]>size[s])s=vec[x][i];//寻找size最大的儿子 } if(s)//能找到size最大的儿子 { top[s]=top[x];//他的儿子结点的链头赋值上它爹 dfs1(s);//继续找重边 } for(int i=0;i<vec[x].size();i++) { if(dad[x]!=vec[x][i]&&vec[x][i]!=s)dfs1(vec[x][i]);//深搜它的轻边的结点里的重边 } } int lca(int x,int y) { for(;top[x]!=top[y];)//不在一个链上 { if(deep[top[x]]<deep[top[y]])swap(x,y); x=dad[top[x]];//将较深点赋值为他链头的爸爸； } if(deep[x]>deep[y])swap(x,y);//深度小的结点为lca return x; } int main() { scanf("%d%d%d",&n,&m,&t);//n个点m条边t个访问； for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); vec[x].push_back(y); vec[y].push_back(x); } dfs(1);//赋值size deep dad dfs1(1);//找重链 轻链 while(t--) { scanf("%d%d",&p,&q); printf("%d ",lca(p,q)); } return 0; }
3、tarjian法
#include<bits/stdc++.h> using namespace std; #define N 10000 vector<int>vec[N]; vector<int>que[N]; int dad[N],far[N],qx[N],qy[N]; int n,m,x,y,ans[N]; int f(int x) { return far[x]==x?x:far[x]=f(far[x]); } void dfs(int x) { far[x]=x; for(int i=0;i<vec[x].size();i++) { if(dad[x]!=vec[x][i]) { dad[vec[x][i]]=x; dfs(vec[x][i]); } } for(int i=0;i<que[x].size();i++) { if(dad[y=qx[que[x][i]]^qy[que[x][i]]]^x)//y是x结点的一个询问；x^x^y=y; { ans[que[x][i]]=f(y); } } far[x]=dad[x]; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d%d",&x,&y); vec[x].push_back(y); vec[y].push_back(x); } for(int i=1;i<=m;i++) { scanf("%d%d",&qx[i],&qy[i]); que[qx[i]].push_back(i);//在每个结点上挂上它的询问是第几个询问； que[qy[i]].push_back(i); } dfs(1); for(int i=1;i<=m;i++) { printf("%d ",ans[i]);//每个询问的答案’ } return 0; }