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

请自觉遵守比赛规则,违者严惩,不接受求情!

问题 J: 古籍研究

问题 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

提示

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