#include<algorithm>
#include<queue>
#include<stdio.h>
#include<vector>
using namespace std;
const int N=560100;
int ver[N],head[N],ed[N],net[N],tot;
int n,m,p;
int fa[N],d[N],v[N],lca[N],ans[N];
vector<int >query[N],query_id[N];
void add(int x,int y)
{
ver[++tot]=y,net[tot]=head[x],head[x]=tot;
}
void add_query(int x,int y,int id)
{
query[x].push_back(y),query_id[x].push_back(id);
query[y].push_back(x),query_id[y].push_back(id);
}
int get(int x)
{
if(x==fa[x])return x;
return fa[x]=get(fa[x]);
}
void tarjan(int x){
v[x]=1;
for(int i=head[x];i;i=net[i])//先遍历下去
{
int y=ver[i];
if(v[y])continue;//说明是父亲
d[y]=d[x]+1;
tarjan(y);
fa[y]=x;//回溯时记录
}
for(int i=0;i<query[x].size();i++)//扫描一遍关于x的所有询问
{
int y=query[x][i],id=query_id[x][i];
if(v[y]==2)
{
int lca=get(y);//找到父亲节点
ans[id]=min(ans[id],lca);//lca这个地方可以根据最后问的方式不同进行修改,大体框架不变
}
}
v[x]=2;//这个节点访问和回溯都完毕了
}
int main()
{
cin>>n>>m>>p;
for(int i=1;i<=n;i++)//预处理一下
{
head[i]=0;
fa[i]=i;
v[i]=0;
query[i].clear(),query_id[i].clear();
}
tot=0;
for(int i=1;i<n;i++)//输入节点
{
int x,y;
cin>>x>>y;
add(x,y);
add(y,x);
}
for(int i=1;i<=m;i++)//输入问题
{
int x,y;
cin>>x>>y;
if(x==y)ans[i]=0;
else{
add_query(x,y,i);
ans[i]=1<<30;
}
}
tarjan(p);//p是根节点
for(int i=1;i<=m;i++)
printf("%d\n",ans[i]);
}
原文:https://www.cnblogs.com/arbor-one/p/12779589.html