LCA

#include<iostream>
#include<cstdio>
#define maxn 500005
using namespace std;
int n,m,s;
int x,y;
int fa[maxn];
int sum1=0,sum2=0;
struct node{
	int head,to,nxt; 
}a[maxn*2];
void add(int x,int y){
	a[++sum1].to=y;
	a[sum1].nxt=a[x].head;
	a[x].head=sum1;
}
struct node2{
	int head,to,nxt; 
}f[maxn*2];
void add2(int x,int y){
	f[++sum2].to=y;
	f[sum2].nxt=f[x].head;
	f[x].head=sum2;
}
int find(int x){
	if(fa[x]==x){
		return x;
	}else{
		return find(fa[x]);
	}
}
bool vis[maxn];
int ans[2*maxn];
void tarjan(int s){
	vis[s]=1;
	for(int i=a[s].head;i;i=a[i].nxt){
		int v=a[i].to;
		if(vis[v]){
			continue;
		}
		tarjan(v);
		fa[v]=s;
	}
	for(int i=f[s].head;i;i=f[i].nxt){
		int v=f[i].to;
		if(vis[v]){
			ans[i]=find(v);
			if(i%2==0){
				ans[i-1]=ans[i];
			}else{
				ans[i+1]=ans[i];
			}
		}
	}
}
int main(){
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<=n;i++){
		fa[i]=i;
	}
	for(int i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		add2(x,y);
		add2(y,x);
	}
	tarjan(s);
	for(int i=1;i<=2*m;i+=2){
		printf("%d\n",ans[i]);
	}
	return 0;
}

LCA

原文：https://www.cnblogs.com/qzhwlzy/p/14736769.html