倍增实现

#include<bits/stdc++.h>
using namespace std;
const int logn=19,maxn=5e5+5;
int d[maxn];
vector<int>u[maxn];
int n,m,x,y,f[maxn][logn],root;
void dfs(int now,int last)
{d[now]=d[last]+1;f[now][0]=last;for(int i=1;i<logn;i++)f[now][i]=f[f[now][i-1]][i-1];for(int i=0;i<u[now].size();i++){int next=u[now][i];if(next==last)continue;dfs(next,now);}return ;
}
int lca(int u,int w)
{if(d[u]>d[w])swap(u,w);for(int i=logn-1;i>=0;i--)if(d[u]<=d[f[w][i]])w=f[w][i];for(int i=logn-1;i>=0;i--){if(f[u][i]==f[w][i])continue;u=f[u][i];w=f[w][i];}if(u==w)return u;return f[u][0];
}	
int main()
{scanf("%d%d%d",&n,&m,&root);for(int i=1;i<=n-1;i++){scanf("%d%d",&x,&y);u[x].push_back(y);u[y].push_back(x);}dfs(root,root);while(m--){scanf("%d%d",&x,&y);
//		cout<<lca(x,y)<<endl;printf("%d\n",lca(x,y));}return 0;
}

tarjan实现

//Tarjan
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+5;
int n,m,x,y,f[maxn],ans[maxn],root;
vector<int>u[maxn],pos[maxn],qs[maxn];
bool vis[maxn];
int getf(int now)
{if(f[now]==now)return now;return f[now]=getf(f[now]);
}
void Tarjan(int now,int last)
{for(int i=0;i<u[now].size();i++){if(u[now][i]==last)continue;Tarjan(u[now][i],now);}vis[now]=true;for(int i=0;i<qs[now].size();i++){if(vis[qs[now][i]]){ans[pos[now][i]]=getf(qs[now][i]);}}f[now]=last;return ;
}
int main()
{scanf("%d%d%d",&n,&m,&root);for(int i=1;i<=n-1;i++){scanf("%d%d",&x,&y);u[x].push_back(y);u[y].push_back(x);}for(int i=1;i<=n;i++)f[i]=i,vis[i]=false;for(int i=1;i<=m;i++){scanf("%d%d",&x,&y);qs[x].push_back(y);qs[y].push_back(x);pos[x].push_back(i);pos[y].push_back(i);}Tarjan(root,root);for(int i=1;i<=m;i++)printf("%d\n",ans[i]);return 0;
}

dfs序实现

//dfs序 
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+5,logn=19;
int d[maxn],f[maxn][logn+2],T[maxn*2],t[maxn][3],len=0,n,m,x,y,root;
vector<int>u[maxn];
void dfs(int now,int last)
{d[now]=d[last]+1;f[now][0]=last;for(int i=1;i<logn;i++)f[now][i]=f[f[now][i-1]][i-1];T[++len]=now;for(int i=0;i<u[now].size();i++){if(u[now][i]==last)continue;dfs(u[now][i],now);}T[++len]=now;return ;
}
int lca(int u,int v)
{if(d[u]>d[v])swap(u,v);if(t[u][0]<=t[v][0]&&t[v][1]<=t[u][1])return u;for(int i=logn-1;i>=0;i--){if(!(t[f[v][i]][0]<=t[u][0]&&t[u][1]<=t[f[v][i]][1]))v=f[v][i];}return f[v][0];
}
int main()
{scanf("%d%d%d",&n,&m,&root);for(int i=1;i<n;i++){scanf("%d%d",&x,&y);u[x].push_back(y);u[y].push_back(x);}d[root]=0;dfs(root,root);memset(t,-1,sizeof(t));for(int i=1;i<=len;i++){if(t[T[i]][0]==-1)t[T[i]][0]=i;else t[T[i]][1]=i;}while(m--){scanf("%d%d",&x,&y);printf("%d\n",lca(x,y));}return 0;
}

【模板】最近公共祖先（LCA） - 洛谷