lxhgww的奇思妙想
描述
lxhgww 在树上玩耍时,LZX2019 走了过来。lxhgww 突然问道:“我现在的k级祖先是谁?”
LZX2019 答道:“不是我吗?”。接着 lxhgww 就用教主之力让 LZX2019 消失了,现在他转过头准备向你求助。
格式
输入格式
第一行包含一个整数N,表示树的结点数。
接下来N-1行包含两个整数X,Y,表示第X个结点和第Y个结点间有一条边。
接下来1行包含一个整数M,表示询问个数。
接下来M行包含两个整数a,b,则x=a^lastans,k=b^lastans。
输出格式
输出包含M行,分别是M个询问的答案。
若没有k级祖先,则输出0
样例
样例输入
5
1 2
2 3
1 4
4 5
5
5 0
6 7
4 5
2 1
4 3
样例输出
5
1
0
1
1
限制
每个测试点1s,512MB
提示
数据范围:
1 ≤ N ≤300000, M ≤ 1800000
1 ≤ x,k≤ N
Source
LZX2019