问题 1347. -- 先祖血脉

1347: 先祖血脉

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

题目描述

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

输入

单组数据
 一个字母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

提示

来源

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