LCATarjan算法
算法步骤：
- 从根开始深搜遍历，入
u时打标记 - 枚举
u的儿子v，遍历完v的子树，回u时把v指向u - 遍历完
u的儿子们，离u时枚举以u为起点的查询，若终点v被搜过，则查找v的根，即u，v的LCA，答案计入ans[] - 递归遍历完整棵树，得到全部查询答案
数组说明：
- e[u]存树边
- query[u]存查询
- fa[u]存父节点
- vis[u]打标记
- ans[i]存结果查询
代码：
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int N=500005,M=2*N;
int n,m,s,a,b;
vector<int> e[N];
vector<pair<int,int>>query[N];
int fa[N],vis[N],ans[M];
int find(int x){
if(x==fa[x]) return x;
return fa[x]=find(fa[x]);
}
void tarjan(int x){
vis[x]=true;//标记x已访问
for(auto y : e[x]){
if(!vis[y]){
tarjan(y);
fa[y]=x;//回到x时指向x
}
}
//离开x时找LCA
for(auto q : query[x]){
int y=q.first,i=q.second;
if(vis[y])ans[i]=find(y);
}
}
int main(){
scanf("%d%d%d", &n,&m,&s);
for(int i=1; i<n; i++){
scanf("%d%d",&a,&b);
e[a].push_back(b);
e[b].push_back(a);
}
for(int i=1;i<=m;i++){
scanf("%d%d",&a,&b);
query[a].push_back({b,i});
query[b].push_back({a,i});
}
for(int i=1;i<=N;i++)fa[i]=i;
tarjan(s);
for(int i=1; i<=m; i++)
printf("%d\n",ans[i]);
return 0;
}