5934: 进阶2.2.1最近公共祖先
内存限制:128 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:37
解决:27
题目描述
一棵树如下图所示,每个节点都标有{1,2,···,16}的整数,节点8是树根。若节点x位于根和y之间的路径中,则x是y的祖先,节点也是自己的祖先。8、4、10和16是16的祖先,8、4、6和7是7的祖先。若x是y的祖先和z的祖先,则x被称为y和z的公共祖先,因此8和4是16和7的公共祖先。若x是y和z的公共祖先并且在它们的公共祖先中最接近y和z,则x被称为y和z的最近公共祖先,16和7的最近公共祖先是4.若y是z的祖先,则y和z的最近公共祖先是y,4和12的最近公共祖先是4.编写一个程序,找到树中两个不同节点的最近公共祖先。
输入
第1行包含一个整数T,表示测试用例的数量。
每个测试用例的第1行都包含整数N(2≤N≤10,000),表示树中的节点数。节点用1~N标记。
接下来的N-1行,每行都包含一对表示边的整数,第1个整数是第2个整数的父节点(有N个节点的树则恰好有N-1条边)。
每个测试用例的最后一行都包含两个不同的整数,求其最近公共祖先。
每个测试用例的第1行都包含整数N(2≤N≤10,000),表示树中的节点数。节点用1~N标记。
接下来的N-1行,每行都包含一对表示边的整数,第1个整数是第2个整数的父节点(有N个节点的树则恰好有N-1条边)。
每个测试用例的最后一行都包含两个不同的整数,求其最近公共祖先。
输出
对每个测试用例,都单行输出两个节点的最近公共祖先。
样例输入 复制
2
16
1 14
8 5
10 16
5 9
4 6
8 4
4 10
1 13
6 15
10 11
6 7
10 2
16 3
8 1
16 12
16 7
5
2 3
3 4
3 1
1 5
3 5
样例输出 复制
4
3