最近公共祖先问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

设计一个算法,对于给定的树中2 个结点,返回它们的最近公共祖先。
对于给定的树T,和树中结点对,计算结点对的最近公共祖先。

Input

输入数据的第1 行有1 个正整数n(n≤50000),表示给定的树有n个顶点,编号为1,2,…,n。编号为1 的顶点是树根。接下来的n 行中,第i+1 行描述与i 个顶点相关联的子结点的信息。每行的第一个正整数k表示该顶点的儿子结点数。其后k个数中,每1 个数表示1个儿子结点的编号。当k=0 时表示相应的结点是叶结点。
第n+2 行是1 个正整数m(m≤30000),表示要计算最近公共祖先的m个结点对。接下来的m行,每行2 个正整数,是要计算最近公共祖先的结点编号。结点编号可能重复出现。

Output

将计算出的m个结点对的最近公共祖先结点编号输出。每行3 个正整数,前2 个是结点对编号,第3 个是它们的最近公共祖先结点编号。

Sample Input

12
3 2 3 4
2 5 6
0
0
2 7 8
2 9 10
0
0
0
2 11 12
0
0
5
3 11
7 12
4 8
9 12
8 10

Sample Output

11 3 1
9 12 6
8 10 2
8 4 1
7 12 2

Hint

Source