问题 1348. -- 古籍研究

1348: 古籍研究

时间限制: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

提示

来源

火辣鸡不会inlcude

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