问题 1348. -- 古籍研究

1348: 古籍研究

时间限制: 1 Sec  内存限制: 128 MB
提交: 19  解决: 12
[提交][状态][讨论版]

题目描述

tsy正在研究古代家族,根据古代文献记载,我们可以知道一些人是直系血亲,这时候一个家族引起了tsy的兴趣,这个家族有N个成员,tsy把他们标记为1到N,这N个成员刚好由N-1
个关系维系,形成了一个树形结构,此时以任何人作为共同祖先都可以形成一个独特的家族谱系,现在给定一个家族关系树,tsy想知道任意x和y在以z为最高公共祖先的情况下的最
近公共祖先是谁?
(友情提示:中国古代实行父系结构,所有文献记录中只有男性成员)

输入

单组数据
第一行一个数字N代表节点的个数
之后N-1行代表关系(保证形成一棵树)
之后一个数字M代表询问次数
之后M行每行三个数字x,y,z和上面说法一致
(1 <= N <= 4e5 , 1 <= M <= 1e5 , 1 <= x, y, z <= N)

输出

输出M行,每行一个数字,代表最近公共祖先

样例输入

10
8 5
9 5
7 5
6 8
3 5
2 9
10 3
4 7
1 10
5
9 10 3
1 5 7
3 4 8
9 10 7
7 10 1

样例输出

3
5
5
5
10

提示

来源

[提交][状态][讨论版]