Tree方面的一个计算问题,Nearest Common Ancestors

Description

A rooted tree is a well-known data structure in computer science and engineering. An example is shown below:

In the figure, each node is labeled with an integer from {1, 2,...,16}. Node 8 is the root of the tree. Node x is an ancestor of node y if node x is in the path between the root and node y. For example, node 4 is an ancestor of node 16. Node 10 is also an ancestor of node 16. As a matter of fact, nodes 8, 4, 10, and 16 are the ancestors of node 16. Remember that a node is an ancestor of itself. Nodes 8, 4, 6, and 7 are the ancestors of node 7. A node x is called a common ancestor of two different nodes y and z if node x is an ancestor of node y and an ancestor of node z. Thus, nodes 8 and 4 are the common ancestors of nodes 16 and 7. A node x is called the nearest common ancestor of nodes y and z if x is a common ancestor of y and z and nearest to y and z among their common ancestors. Hence, the nearest common ancestor of nodes 16 and 7 is node 4. Node 4 is nearer to nodes 16 and 7 than node 8 is.

For other examples, the nearest common ancestor of nodes 2 and 3 is node 10, the nearest common ancestor of nodes 6 and 13 is node 8, and the nearest common ancestor of nodes 4 and 12 is node 4. In the last example, if y is an ancestor of z, then the nearest common ancestor of y and z is y.

Write a program that finds the nearest common ancestor of two distinct nodes in a tree.

Input

The input consists of T test cases. The number of test cases (T) is given in the first line of the input file. Each test case starts with a line containing an integer N , the number of nodes in a tree, 2<=N<=10,000. The nodes are labeled with integers 1, 2,..., N. Each of the next N -1 lines contains a pair of integers that represent an edge --the first integer is the parent node of the second integer. Note that a tree with N nodes has exactly N - 1 edges. The last line of each test case contains two distinct integers whose nearest common ancestor is to be computed.
Output

Print exactly one line for each test case. The line should contain the integer that is the nearest common ancestor.
Sample Input

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
Sample Output

4
3

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问

相似问题

0
根据输入的m和n的值计算树的高度,怎么运用C语言的程序设计代码程序的编写的方式实现的呢?
0
最接近并且超过金额的数量的计算,怎么用C语言的程序的设计的代码的方式来实现的呢?
0
计算车站的修建的位置,采用C语言的程序的编写设计的代码去实现位置的计算
0
计算乘坐汽车所需要的时间的问题,怎么用C语言的程序的代码设计的编写的思想的方法来实现的呢
0
计算三个天体什么时候对齐的一个算法的问题,怎么采用C语言的程序的设计的编写的过程的方法来计算怎么做的
0
计算距离的浮点的表示的计算问题,怎么用C语言的程序的设计的代码来实现的
0
数据结构里面编写代码实现道路的长度的存储计算求出通过的结论怎么用C语言的程序的设计的代码的形式
1
Geoserver如何发布Postgresql中带时间序列的栅格数据
0
用C语言,The nearest fraction
0
用C语言 The nearest fraction
0
远足的计算问题寻找路线怎么用 C语言
0
Fairies' Defence的一个编写的代码问题
0
C语言代码编程方法,Little Wish~ lyrical step~
0
Little Wish~ lyrical step~的过程的编写技术
0
Wow! Such Sequence!是怎么编写的
1
NumpyArrayIterartor 输入维度问题
0
The nearest fraction 算法怎么解答
0
Moonmist 程序的计算,请认真回答,否则一律举报
0
字符和图形问题的结合,If You are my legend
0
金额的计算的问题,Loan