2014.软院.Problem C. 最近公共祖先

我就是我 2023-07-18 14:12 17阅读 0赞

**题目描述**  
给出一棵有N个节点的有根树TREE（根的编号为1），对于每组查询，请输出树上节点u和v的最近公共祖先。  
最近公共祖先：对于有向树TREE的两个结点u,v。最近公共祖先LCA（TREE u,v）表示一个节点x，满足x是u、v的祖先且x的深度尽可能大。

**输入格式**  
输入数据第一行是一个整数T（1<=T<=100），表示测试数据的组数。  
对于每组测试数据：  
第一行是一个正整数N（1<=N<=100），表示树上有N个节点。  
接下来N-1行，每行两个整数u,v(1<=u,v<=N)，表示节点u是v的父节点。  
接下来一行是一个整数M（1<=M<=1000），表示查询的数量。  
接下来M行，每行两个整数u,v(11<=u,v<=N)，表示查询节点u和节点v的最近公共祖先。

**输出格式**  
对于每个查询，输出一个整数，表示最近公共祖先的编号，

**输入样例**

2
    3
    1 2
    1 3
    1
    2 3
    4
    1 2
    1 3
    3 4
    2
    2 3
    3 4

**输出样例**

1
    1
    3

#include<bits/stdc++.h>
    using namespace std;
    int main() { 
    	int T,N,M;
    	int u,v;
    	int t[105];
    	scanf("%d",&T);
    	while(T--) { 
    		memset(t,0,sizeof(t));
    		scanf("%d",&N);
    		N--;
    		while(N--) { 
    			scanf("%d %d",&u,&v);// u -> v
    			t[v]=u;
    		}
    		cin>>M;
    		while(M--) { 
    			stack<int> s1;
    			stack<int> s2;
    			scanf("%d %d",&u,&v);
    			while(u) { 
    				s1.push(u);
    				u=t[u];
    			}
    			while(v) { 
    				s2.push(v);
    				v=t[v];
    			}
    			int ans=1;
    			while(!s1.empty()&&!s2.empty()&&s1.top()==s2.top()) { 
    				ans=s1.top();
    				s1.pop();
    				s2.pop();
    			}
    			printf("%d\n",ans);
    		}
    	}
    	return 0;
    }