1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=300005,K=20;
int n,m,Depth[maxn],Maxdep[maxn],p[maxn][K],Son[maxn],Len[maxn],Top[maxn],highbit[maxn],lastans=0;
bool vst[maxn];
vector<int> edges[maxn],Up[maxn],Down[maxn];
void AddEdge(int x,int y) {
edges[x].push_back(y);
}
void Dfs1(int Now,int fa,int depth) {
Maxdep[Now]=Depth[Now]=depth;
p[Now][0]=fa;
for(int j=1; j<K; j++)
if(p[Now][j-1])p[Now][j]=p[p[Now][j-1]][j-1];
else break;
for(int Next:edges[Now]) {
if(Next==fa)continue;
Dfs1(Next,Now,depth+1);
if(Maxdep[Next]>Maxdep[Son[Now]]) {
Son[Now]=Next;
Maxdep[Now]=Maxdep[Next];
}
}
}
void Dfs2(int Now,int top,int len) {
Top[Now]=top;
Len[Now]=len;
if(Son[Now]) {
Dfs2(Son[Now],top,len+1);
Len[Now]=Len[Son[Now]];
}
for(int Next:edges[Now]) {
if(Next==p[Now][0]||Next==Son[Now])continue;
Dfs2(Next,Next,1);
}
}
int Query(int Now,int kth) {
if(kth>Depth[Now])return 0;
if(!kth)return Now;
Now=p[Now][highbit[kth]],kth^=(1<<highbit[kth]);
if(!kth)return Now;
if(Depth[Now]-Depth[Top[Now]]==kth)return Top[Now];
if(Depth[Now]-Depth[Top[Now]]>kth)return Down[Top[Now]][Depth[Now]-Depth[Top[Now]]-kth-1];
return Up[Top[Now]][kth-(Depth[Now]-Depth[Top[Now]])-1];
}
int main() {
n=Get_Int();
for(int i=1; i<n; i++) {
int x=Get_Int(),y=Get_Int();
AddEdge(x,y);
AddEdge(y,x);
}
Dfs1(1,0,1);
Dfs2(1,1,1);
for(int i=1; i<=n; i++) {
int top=Top[i];
if(!vst[top]) {
vst[top]=1;
int l=0,now=top;
while(l<Len[top]&&now) {
now=p[now][0];
l++;
Up[top].push_back(now);
}
l=0,now=top;
while(l<Len[top]) {
now=Son[now];
l++;
Down[top].push_back(now);
}
}
}
int Max=1;
for(int i=1; i<=n; i++) {
if(i>>Max&1)Max++;
highbit[i]=Max-1;
}
m=Get_Int();
for(int i=1; i<=m; i++) {
int x=Get_Int()^lastans,y=Get_Int()^lastans;
printf("%d\n",lastans=Query(x,y));
}
return 0;
}
|
