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

请自觉遵守比赛规则，违者严惩，不接受求情！
问题 I: 先祖血脉

问题 I: 先祖血脉

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

题目描述

又到了一年一度祭祀先祖的日子，这个时候全家族的人会齐聚到祠堂，每个家族的人都可以看做一颗树的节点，根则是所有人的祖先，按照村里的习俗，两人见面寒暄的第一句话是
介绍自己的脉系并寻找两人最近的公共祖先，然而家族成员太多了，所他们犯了难，并求助与你，你能帮帮他们寻找到先祖吗？

输入

单组数据
一个字母N代表家族成员数
之后N-1行每行两个字母u，v(1 <= u, v <= N)代表这两个人是直系亲属，1是所有人的先祖。
之后一个字母M代表询问次数
之后M行每行两个数u, v代表询问的家族成员编号
(1 <= N <= 4e5, 1 <= M <= 1e5)

输出

输出M行，每行是每个询问的两个村民的最近公共祖先

样例输入

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

样例输出

2 4 4 2 4

提示

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