这是我的倍增这是评测记录

#include<cstdio>
#include<cmath>
using namespace std;
const int MAXN=5e5;
const int MAXL=log2(MAXN)+10;
struct edge{
	int to,nxt;
}e[MAXN*2+10];
int n,q,s,lg,cnt,hd[MAXN+10],d[MAXN+10],f[MAXN+10][MAXL+10];
bool vis[MAXN+10];
void myswap(int &x,int &y){
	x^=y;
	y^=x;
	x^=y;
	return;
}
void add(int u,int v){
	++cnt;
	e[cnt].to=v;
	e[cnt].nxt=hd[u];
	hd[u]=cnt;
	return;
}
void dfs(int x,int lst){
	vis[x]=true;
	d[x]=d[lst]+1,f[x][0]=lst;
	for(int i=1;(1<<i)<=d[x];i++)
		f[x][i]=f[f[x][i-1]][i-1];
	for(int i=hd[x];i;i=e[i].nxt)
		if(!vis[e[i].to])
			dfs(e[i].to,x);
	return;
}
int lca(int x,int y){
	if(x==y)
		return x;
	if(d[x]<d[y])
		myswap(x,y);
	for(int i=lg;i>=0;i--)
		if(d[x]-(1<<i)>=d[y])
			x=f[x][i];
	if(x==y)
		return x;
	for(int i=lg;i>=0;i--)
		if(f[x][i]!=f[y][i])
			x=f[x][i],y=f[y][i];
	return f[x][0];
}
int main(){
	scanf("%d%d%d",&n,&q,&s);
	lg=log2(n);
	for(int i=1;i<n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);
		add(v,u);
	}
	dfs(s,0);
	for(int i=1;i<=q;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		printf("%d\n",lca(x,y));
	}
	return 0;
}

这是我的Tarjan这是评测记录

#include<cstdio>
using namespace std;
const int MAXN=5e5;
struct edge{
	int to,nxt;
}e[MAXN*2+10],qry[MAXN*2+10];
int n,q,s,ans[MAXN+10],cnt,hde[MAXN+10],hdq[MAXN+10],id[MAXN+10],fa[MAXN+10];
bool vis[MAXN+10];
int fr(int x){
	int root=x;
	while(root!=fa[root])
		root=fa[root];
	while(fa[x]!=x){
		int t=x;
		x=fa[x];
		fa[t]=root;
	}
	return root;
}
void adde(int u,int v){
	++cnt;
	e[cnt].to=v;
	e[cnt].nxt=hde[u];
	hde[u]=cnt;
	return;
}
void addq(int x,int y,int i){
	++cnt;
	qry[cnt].to=y;
	qry[cnt].nxt=hdq[x];
	hdq[x]=cnt;
	id[cnt]=i;
	return;
}
void tarjan(int x){
	vis[x]=true;
	for(int i=hde[x];i;i=e[i].nxt)
		if(!vis[e[i].to]){
			tarjan(e[i].to);
			fa[e[i].to]=x;
		}
	for(int i=hdq[x];i;i=qry[i].nxt)
		if(vis[qry[i].to])
			ans[id[i]]=fr(qry[i].to);
	return;
}
int main(){
	scanf("%d%d%d",&n,&q,&s);
	for(int i=1;i<=n;i++)
		fa[i]=i;
	for(int i=1;i<n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		adde(u,v);
		adde(v,u);
	}
	cnt=0;
	for(int i=1;i<=q;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		addq(x,y,i);
		addq(y,x,i);
	}
	tarjan(s);
	for(int i=1;i<=q;i++)
		printf("%d\n",ans[i]);
	return 0;
}

T了3个,蛙了4个 求解，悬关！