OpenJudge

lca02:求最近公共祖先(LCA)

总时间限制:
1000ms
内存限制:
102400kB
描述

树是在计算机科学领域中非常重要的数据结构。一个树的形式如下所示:

说明: http://media.openjudge.cn/images/1330_1.jpg

在上图中,树中每个节点的编号都是一个整数{ 1216 }8是树的根节点。当从根节点到y节点的路径中经过节点x,那么节点x称作是节点y的祖先。

例如,节点4是节点16的祖先。同样,节点10也是节点16的祖先。事实上,节点41016都是节点16的祖先。注意,一个节点是其本身的一个祖先。节点8467是节点7的祖先节点。如果节点x既是两个不同节点yz的祖先,那么称节点x是节点yz的公共祖先。因此,节点84都是节点167的公共祖先。

当节点x是节点yz所有公共祖先中距离yz最近的节点,那么称节点x是节点yz的最近公共祖先。因此,节点4是节点167的最近公共祖先,因为节点4比节点8更接近节点167

其他例子,最近的共同祖先节点23是节点10日最近的共同祖先节点的节点6138,和最近的共同祖先节点412是节点4。在最后一个例子,如果yz的祖先,那么yz的最近的共同祖先是y

编写一个程序,求出树中两个节点的最近公共祖先。


输入
第一行输入一个整数T,表示测试样例的组数。
每组测试样例第一行包含一个整数N,N表示节点的个数, 2 <= N <= 10000。节点编号为1、2、……、n。
接下来的N-1行输入树中每条边的信息,每行包含2个数,第一个节点表示为第二个节点的父节点。
接下来输入一个整数M,表示询问的个数。
下面的M行中每行输入两个整数u和v,表示待查询两个节点的编号。
输出
每个测试样例输出M行,表示对应查询节点的最近公共祖先。
样例输入
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
5
7 16
9 1
11 2
7 11
16 3
5
2 3
3 4
3 1
1 5
3
3 5
4 1
2 5
样例输出
4
8
10
4
16
3
3
2
全局题号
14582
添加于
2017-04-13
提交次数
16
尝试人数
4
通过人数
4