Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:32 MB

#857. 最近公共祖先

Statistics

给你一棵有根树,求出这棵树上若干对节点的最近公共祖先。两个节点共同拥有的祖先叫做它们的公共祖先,它们公共祖先中离它们最近的一个叫做它们的最近公共祖先。
Input
输入只包含正整数。
第一行两个数n,m(均不超过100000),表示树的节点个数和询问个数。树的节点从1到n编号。
接下来n行,描述这n个点的儿子节点。每行第一个数k,表示这个点儿子的个数。接下来k个数,分别为这个点的儿子。
接下来m行,描述m个询问。每行两个数a,b,表示询问a和b的最近公共祖先。
输入保证是一棵以1为根的树。所有表示节点的数均不超过[1,n]。
Output
m行,为输入中对应询问的答案。
Sample Input

10 10
4 3 2 4 5 
0 
0 
1 8 
1 6 
0 
0 
3 10 9 7 
0 
0 
7 7
7 6
4 8
10 8
1 3
2 3
3 4
6 1
9 1
5 3
Sample Output
7
1
4
8
1
1
1
1
1
1