学了好久（一两个星期）都没彻底搞懂的lca，今天总算理解了。就来和大家分享下我自己的心得
首先，如果你还不懂什么是lca，出门左转自行百度
首先讲倍增
倍增的思想很简单，首先进行预处理，用一个深搜将每个点的深度和它向上跳一步到达的点（也就是它的父节点）处理出来，然后用下列递推式
f[i][j]=f[f[i][j-1]][j-1]
求出该点跳2^j步所到达的点。这里解释一下，为什么是f[f[i][]j-1][j-1]？因为倍增每次都是跳的2的整数次幂步，而2^j=2^(j-1)+2^(j-1);这样就不难理解了。
然后，对于每两个询问的点，只需要先找出那个点的深度更深，就将它跳跃到与另一个点深度相同，如果此时两个点相同，那么这个点就是最近公共祖先;如果不相同，两个点就一起跳，直找到最近公共祖先为止。
上代码：
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<algorithm> #define N 500005 using namespace std; int n,m,s,d[N],f[N][20],head[N]; struct Edge{ int from,to,next; }edge[N*2]; inline int read() { char ch=getchar();int num=0; if(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9') {num=num*10+ch-'0'; ch=getchar();} return num; } int anum=1; void add(int x,int y) {edge[anum].to=y; edge[anum].next=head[x]; head[x]=anum++;} void dfs(int u) { for(int i=head[u];i!=-1;i=edge[i].next) { int ne=edge[i].to; if(d[ne]==0) {d[ne]=d[u]+1; f[ne][0]=u; dfs(ne);} } } void init() { 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 a,int b) { if(d[a]<d[b]) swap(a,b); for(int i=19;i>=0;i--) {if(d[f[a][i]]>=d[b]) a=f[a][i];} if(a==b) return a; for(int i=19;i>=0;i--) if(f[a][i]!=f[b][i]) a=f[a][i],b=f[b][i]; return f[a][0]; } int main() { memset(head,-1,sizeof(head)); n=read();m=read();s=read(); for(int i=1;i<n;i++) {int x,y; x=read();y=read(); add(x,y);add(y,x);} d[s]=1; dfs(s);init(); for(int i=1;i<=m;i++) {int a,b; a=read();b=read(); printf("%d ",lca(a,b));} return 0; }
关于tarjan，具体思想我在另外一篇博客中已经讲过了，这里就只放代码，思路请转：这里
下面是代码：
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #define N 500005 #define M 1000001 using namespace std; int n,m,s,cnt1,cnt2; int dad[N],ans[N]; bool used[N]; struct edge{ int v,num,next; }e1[M],e2[M]; struct road{ int head; }v1[N],v2[N]; void before() { memset(v1,-1,sizeof(v1)); memset(v2,-1,sizeof(v2)); memset(used,false,sizeof(used)); memset(dad,-1,sizeof(dad)); } int find(int x) { return dad[x]==-1?x:dad[x]=find(dad[x]); } void together(int x,int y) { int f1=find(x); int f2=find(y); if(f1!=f2) dad[y]=x; } void v1add(int x,int y) { e1[cnt1].v=y; e1[cnt1].next=v1[x].head; v1[x].head=cnt1++; } void v2add(int x,int y,int z) { e2[cnt2].v=y; e2[cnt2].num=z; e2[cnt2].next=v2[x].head; v2[x].head=cnt2++; } void tarjan(int u) { used[u]=true; for(int i=v1[u].head;i!=-1;i=e1[i].next) { int v=e1[i].v; if(used[v]) continue; tarjan(v); together(u,v); } int sum; for(int i=v2[u].head;i!=-1;i=e2[i].next) { int v=e2[i].v; sum=e2[i].num; if(used[v]) ans[sum]=find(v); } } int main() { int u,v; scanf("%d%d%d",&n,&m,&s); before(); int nn=n; nn--; while(nn--) { scanf("%d%d",&u,&v); v1add(v,u);v1add(u,v); } for(int i=1;i<=m;i++) { scanf("%d%d",&u,&v); v2add(u,v,i);v2add(v,u,i); } tarjan(s); for(int i=1;i<=m;i++) printf("%d ",ans[i]); return 0; }