1 //tarjian离线求LCA 2 #include<cstdio> 3 #define N 420000 4 struct hehe{ 5 int next; 6 int to; 7 int lca; 8 }; 9 hehe edge[N];//树的链表 10 hehe qedge[N];//需要查询LCA的两节点的链表 11 int n,m,p,x,y; 12 int num_edge,num_qedge,head[N],qhead[N]; 13 int father[N]; 14 int visit[N];//判断是否被找过 15 void add_edge(int from,int to){//建立树的链表 16 edge[++num_edge].next=head[from]; 17 edge[num_edge].to=to; 18 head[from]=num_edge; 19 } 20 void add_qedge(int from,int to){//建立需要查询LCA的两节点的链表 21 qedge[++num_qedge].next=qhead[from]; 22 qedge[num_qedge].to=to; 23 qhead[from]=num_qedge; 24 } 25 int find(int z){//找爹函数 26 if(father[z]!=z) 27 father[z]=find(father[z]); 28 return father[z]; 29 } 30 int dfs(int x){//把整棵树的一部分看作以节点x为根节点的小树 31 father[x]=x;//由于节点x被看作是根节点，所以把x的father设为它自己 32 visit[x]=1;//标记为已被搜索过 33 for(int k=head[x];k;k=edge[k].next)//遍历所有与x相连的节点 34 if(!visit[edge[k].to]){//若未被搜索 35 dfs(edge[k].to);//以该节点为根节点搞小树 36 father[edge[k].to]=x;//把x的孩子节点的father重新设为x 37 } 38 for(int k=qhead[x];k;k=qedge[k].next)//搜索包含节点x的所有询问 39 if(visit[qedge[k].to]){//如果另一节点已被搜索过 40 qedge[k].lca=find(qedge[k].to);//把另一节点的祖先设为这两个节点的最近公共祖先 41 if(k%2)//由于将每一组查询变为两组，所以2n-1和2n的结果是一样的 42 qedge[k+1].lca=qedge[k].lca; 43 else 44 qedge[k-1].lca=qedge[k].lca; 45 } 46 } 47 int main(){ 48 scanf("%d%d%d",&n,&m,&p);//输入节点数，查询数和根节点 49 for(int i=1;i<n;++i){ 50 scanf("%d%d",&x,&y);//输入每条边 51 add_edge(x,y); 52 add_edge(y,x); 53 } 54 for(int i=1;i<=m;++i){ 55 scanf("%d%d",&x,&y);//输入每次查询，考虑(u,v)时若查找到u但v未被查找，所以将(u,v)(v,u)全部记录 56 add_qedge(x,y); 57 add_qedge(y,x); 58 } 59 dfs(p);//进入以p为根节点的树的深搜 60 for(int i=1;i<=m;i++) 61 printf("%d ",qedge[i*2].lca);//两者结果一样，只输出一组即可 62 return 0; 63 }