KEKE的树
描述
KEKE有一棵以1为根的树,这棵树有n个结点。
KEKE每次想询问你编号在[L,R]区间的lca。
格式
输入格式
第一行包含一个整数n,表示这棵树有n个结点。
第2行~第n行每行包含两个整数,表示一条树上的边。
接下来的一行包含一个整数q,表示有q组询问。
接下来q行每行包含两个整数L、R,表示询问。
输出格式
对于每个询问输出他们的公共lca。(若L==R输出本身)
样例
样例输入
10
1 2
1 8
2 3
2 7
3 4
3 5
3 6
8 9
8 10
5
4 6
4 7
3 7
9 10
7 9
样例输出
3
2
2
8
1
限制
每个测试点1s,256MB
提示
数据范围:1≤n,q≤2*10^5+5
Source
KEKE_046 && Bill_Yang