include

	#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]);
	}

lca的tarjan算法

原文：https://www.cnblogs.com/arbor-one/p/12779589.html