主页 讨论版 问题 名次 状态 统计

请自觉遵守比赛规则，违者严惩，不接受求情！
古籍研究-j9国际集团直营

问题 J: 古籍研究

时间限制: 1000 ms  内存限制: 128 MB
提交: 25  解决: 14
[提交][状态][讨论版]

题目描述

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

提示

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