OpenJudge

lca03:求树中两点最短距离(LCA)

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

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


假设树中的边长都为1,编写一个程序,求出树中两个节点之间的最短距离。


输入
第一行输入一个整数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
3
2
4
1
2
2
3
全局题号
14583
添加于
2017-04-13
提交次数
2
尝试人数
2
通过人数
0