例题：洛谷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;
}