1 #include <iostream>
2 #include <cstdio>//标准输入输出 
3 using namespace std;
4 int n,m,s,cnt;//cnt为边计数器 
5 int head[500005];//链式前向星 
6 int qhead[500005];//链式前向星 (询问) 
7 int f[500005];//并查集储存父结点
8 int vis[500005];//判断是否访问过 
9 int lca[1000005];//离线存储答案 

 1 struct edge
 2 {
 3     int nxt;
 4     int to;
 5     //int dis;边权值默认为 1 
 6 }e[1000005];//建议4倍 
 7 
 8 struct qedge
 9 {
10     int nxt;
11     int to;
12     //int dis;
13 }qe[1000005];//建议4倍 
14 
15 void add(int x,int y/*,int d*/)
16 {
17     e[++cnt].nxt=head[x];
18     e[cnt].to=y;
19     head[x]=cnt;
20 }//链式前向星加边 
21 
22 void qadd(int x,int y)
23 {
24     qe[++cnt].nxt=qhead[x];
25     qe[cnt].to=y;
26     qhead[x]=cnt;
27 }//链式前向星加边 (询问) 

 1 int find(int x)
 2 {
 3     return f[x]== x ? x : f[x] = find( f[x] );//路径压缩 
 4 }//“查 ” 
 5 
 6 void merge(int a,int b)
 7 {
 8     int fa=find(a),fb=find(b);
 9     if(fa==fb)
10     return ;
11     f[fa]=fb;
12 }//“并 ” 
13 
14 void setup(int N)
15 {
16     for(int i=1;i<=N;i++)
17     {
18         f[i]=i;
19     }
20 }//初始化 

 1 void tarjan(int x)
 2 {
 3     cout<<"#访问节点:"<<x<<endl;
 4     vis[x]=1;//标记访问 
 5     for(int i=head[x];i;i=e[i].nxt)//遍历此子节点所有出边 
 6     {
 7         int v=e[i].to;
 8         if(!vis[v])//如下一节点未访问 
 9         {
10             tarjan(v);//继续遍历 
11             f[v]=x;//回溯时更新子节点祖先 
12             if(v==11)
13             {
14                 cout<<"//"<<x<<" "<<f[11]<<endl;
15             }
16         }
17     }
18     for(int i=qhead[x];i;i=qe[i].nxt)//对于询问中有此点的询问组 
19     {
20         int qv=qe[i].to;
21         if(vis[qv])//若另一询问节点已被遍历 
22         {
23             lca[i]=find(qv);//则对于这组询问，其LCA为另一询问节点最后一次更新的祖先 
24             if(i%2)//对于正反两组相同询问  
25                 lca[i+1]=lca[i];//若为正向的询问，下一组询问为此次询问的反向询问 ，询问结果相同 
26             else
27                 lca[i-1]=lca[i];//若为反向的询问，下一组询问为此次询问的正向询问 ，询问结果相同 
28         }
29     }
30 }//DFS函数 

 1 int main()
 2 {
 3     cin>>n>>m>>s;
 4     for(int i=1;i<n;i++)
 5     {
 6         int a,b;
 7         cin>>a>>b;
 8         add(a,b);//无向图正反存边 
 9         add(b,a);
10     }
11     cnt=0;//懒得再加一个变量qcnt 
12     for(int i=1;i<=m;i++)
13     {
14         int a,b;
15         cin>>a>>b;
16         qadd(a,b);//储存正反询问 
17         qadd(b,a);//无向图正反存边 
18     }
19     setup(n);//初始化 
20     tarjan(s);//以s为根开始遍历 
21     for(int i=1;i<=m;i++)
22     {
23         printf("%d\n",lca[i*2]);//由于每组询问储存了两遍，所以输出时输出其中一组 
24     }
25     return 0;
26 }