先祖血脉-j9国际集团直营

1347: 先祖血脉

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

提示

来源

火辣鸡不会include

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