最近公共祖先 Tarjan算法

例题：洛谷P3379 【模板】最近公共祖先（LCA）
https://www.luogu.com.cn/problem/P3379

tarjan算法是利用了并查集来求LCA的，时间复杂度比倍增低，是O(n+m)

#include<iostream>
#include<vector>
#include<utility>
#define forup(i,l,r) for(int i=l;i<=r;i++)
#define fordown(i,l,r) for(int i=r;i>=l;i--)
using namespace std;
const int N =5e5+5;
vector<int> child[N];//结点所连结点，此处为无向边 
vector<pair<int,int>> query[N];//询问组 
int fa[N];
bool vis[N];
int ans[N];//第n组询问的答案 
int read()
{
	int n=0;
	char m=getchar();
	while(m<'0'||m>'9') m=getchar();
	while(m>='0'&&m<='9'){
		n=(n<<1)+(n<<3)+(m^'0');
		m=getchar();
	}
	return n;
}
int find(int a)
{
	return fa[a]==a?a:fa[a]=find(fa[a]);
}
void tarjan(int u)
{
	vis[u]=true;//先标记 
	for(int c:child[u])//访问子节点，这里应该算是一个前序遍历，不过用了回溯，对每个结点的处理是后序遍历的
	{
		if(!vis[c]){
			tarjan(c);
			fa[c]=u;//回溯 
		}
	}
	for(pair<int,int> q:query[u])
	{
		int v=q.first,i=q.second;
		if(vis[v]) ans[i]=find(v);//由于回溯，相当于是从最左下的子树开始连fa，于是如果已经被遍历的话，那么这个子树的根就应该是u和v的最近公共祖先 
	}
}
int main()
{
	int n,m,root;
	n=read(),m=read(),root=read();
	forup(i,1,n-1)//存边 
	{
		int u,v;
		u=read(),v=read();
		child[u].push_back(v);
		child[v].push_back(u);
	}
	forup(i,1,m)//存询问 
	{
		int u,v;
		u=read(),v=read();
		query[u].push_back({v,i});
		query[v].push_back({u,i});//因为必然会有另外一个还没有vis的情况，于是要存双向的
	}
	forup(i,1,n) fa[i]=i;
	tarjan(root);
	forup(i,1,m) cout<<ans[i]<<endl;
	return 0;
 } 

参考：https://www.cnblogs.com/dx123/p/16320465.html