解题思路

1. 结构体定义：
   • vnode 结构体表示顶点节点，包含 firstedge 成员，用于存储该顶点的第一条边的索引。
   • enode 结构体表示边节点，包含 v 成员（表示边的目标顶点）和 next 成员（指向下一条边的索引）。
2. 寻找最近公共祖先函数 findlca：
   • 如果当前节点 p 是输入的节点 a 或 b，则返回 p。
   • 如果当前节点 p 没有边（即 vv[p].firstedge == -1），则返回 0。
   • 初始化 afind 和 bfind 为 false，用于标记是否找到节点 a 和 b。
   • 遍历当前节点 p 的边，递归调用 findlca 处理子节点 son。
   • 如果子节点中找到 a，则设置 afind 为 true；如果找到 b，则设置 bfind 为 true；如果子节点中找到最近公共祖先（即 t > 0），则直接返回 t。
   • 遍历完所有子节点后，如果 afind 和 bfind 都为 true，则返回当前节点 p；否则，根据 afind 和 bfind 的情况返回 a 或 b 或 0。
3. 主函数 main：
   • 读取测试用例数量 nc。
   • 对于每个测试用例：
     • 读取节点数量 n，初始化顶点节点的 firstedge 为 -1，边节点的 next 为 -1，并初始化每个节点的父节点为自身（fa[i] = i）。
     • 读取 n - 1 条边的信息，构建邻接表表示的树，同时更新每个节点的父节点。
     • 找到树的根节点 rt（即没有父节点的节点）。
     • 读取需要查找最近公共祖先的两个节点 a 和 b，调用 findlca 函数找到它们的最近公共祖先，并输出结果。

#include<iostream>
using namespace std;

struct vnode{
	int firstedge;
}vv[10001];

struct enode{
	int v,next;
}ee[10001];

int rt,n,a,b,fa[10001];

int findlca(int p){
	if(p==a||p==b)
		return p;
	if(vv[p].firstedge==-1)
		return 0;
	
	bool afind =0, bfind = 0;
	for(int i = vv[p].firstedge; i!=-1; i = ee[i].next){
		int son = ee[i].v, t = findlca(son);
		if(t==a)
			afind = 1;
		else if(t==b)
			bfind = 1;
		else if(t>0)
			return t;
	}
	
	if(afind&&bfind)
		return p;
	return afind?a:(bfind?b:0);
}


int main(){
	int nc;
	cin>> nc;
	while(nc--){
		cin >> n;
		for(int i = 1; i <= n; i++)
			vv[i].firstedge = -1, ee[i].next = -1;
		
		for(int i = 1; i <= n; i++)
			fa[i] = i;
		int cnt = 0;
		for(int i = 0; i < n-1; i++){
			int u,v;
			cin >> u>> v;
			fa[v] = u;
			ee[cnt].v = v;
			ee[cnt].next = vv[u].firstedge;
			vv[u].firstedge = cnt;
			cnt++;
		}
		
		for(int i = 1; i <= n; i++)
			if(fa[i]==i){
			rt = i;
			break;
		}
		cin >> a >> b;
		cout << findlca(rt) << endl;
	}
}