893F. Subtree Minimum Query[倍增,线段树]

You are given a rooted tree consisting of $n$ vertices. Each vertex has a number written on it; number $a_i$ is written on vertex $i$.

Let’s denote $d_{i,j}$ as the distance between vertices $i$ and $j$ in the tree (that is, the number of edges in the shortest path from $i$ to $j$). Also let’s denote the $k$-blocked subtree of vertex $x$ as the set of vertices $y$ such that both these conditions are met:

  • $x$ is an ancestor of $y$ (every vertex is an ancestor of itself);
  • $d_{x,y}$ ≤ $k$.

You are given $m$ queries to the tree. $i$-th query is represented by two numbers $x_i$ and $k_i$, and the answer to this query is the minimum value of $a_j$ among such vertices $j$ such that $j$ belongs to $k_i$-blocked subtree of $x_i$.

Write a program that would process these queries quickly!

Note that the queries are given in a modified way.

Input

The first line contains two integers $n$ and $r$ ($1 ≤ r ≤ n ≤ 100000$) — the number of vertices in the tree and the index of the root, respectively.

The second line contains $n$ integers $a_1$, $a_2$, …, $a_n$ ($1 ≤ a_i ≤ 10^9$) — the numbers written on the vertices.

Then $n$ - 1 lines follow, each containing two integers $x$ and $y$ ($1 ≤ x,y ≤ n$) and representing an edge between vertices $x$ and $y$. It is guaranteed that these edges form a tree.

Next line contains one integer $m$ ($1 ≤ m ≤ 10^6$) — the number of queries to process.

Then $m$ lines follow, $i$-th line containing two numbers $p_i$ and $q_i$, which can be used to restore $i$-th query ($1 ≤ p_i, q_i ≤ n$).

$i$-th query can be restored as follows:

Let $last$ be the answer for previous query (or $0$ if $i = 1$). Then $x_i = ((p_i + last) \mod n) + 1$, and $k_i = (q_i + last) \mod n$ .

Output

Print $m$ integers. $i$-th of them has to be equal to the answer to $i$-th query.

Example

input

1
2
3
4
5
6
7
8
9
5 2
1 3 2 3 5
2 3
5 1
3 4
4 1
2
1 2
2 3

output

1
2
2
5

题解

题目大意:给你一棵树,每个点有一个点权,对于没一组询问 $x$,$y$,求以x为根,距离 $x \le y$ 的点的点权的 $min$,强制在线

这是一道很好想的工业题(大雾)

开始就相当倍增,$f_{i,d}$ 表示以 $d$为根, 其子树与他距离 $\le 2^i$的 $min$
之后再用st表的方式去暴力搞?

随机的数据可以过?不会很慢?然而有hack的数据.

然后听说要用线段树,于是就相当搞个bfs序,来维护某一段区间的 $min$

于是我建了$\log_2 n$棵线段树

后面发现找左端点和右端点挺麻烦的,然后看了absi的博客,发现不如找的时候直接记答案,没必要多搞一些东西了.
为了方便(为了偷懒),把自己的深度记为1
时间复杂度 $O(n \log_2 n^3+m \log_2 n^2)$ (装作没写错)
细节处理要注意,调了很久.
代码

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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include<bits/stdc++.h>
using namespace std;
int read()
{
char s;int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
if(s==EOF)exit(0);if(s=='-')base=-1,s=getchar();
while(s>='0'&&s<='9') {k=k*10+(s-'0');s=getchar();}
return k*base;
}
void write(int x)
{
if(x<0) {putchar('-');write(-x);}
else {if(x/10)write(x/10);putchar(x%10+'0');}
}
inline void qmax(int &x,int y) {if (y>x) x=y;}
inline void qmin(int &x,int y) {if (y<x) x=y;}
const int INF=1e9+100;
const int maxn=1e5+1000;

int n,root,X,Y,Z;
int to[maxn<<1],ne[maxn<<1],po[maxn],iddd;
inline void add(int x,int y)
{
iddd++;
to[iddd]=y;ne[iddd]=po[x];po[x]=iddd;
}
int a[maxn];
int q[maxn],l1,r1,/*队列*/dfn[maxn]/*bfs序*/;
bool vis[maxn];
int Min[maxn],L1[maxn],R1[maxn];
int t[18][maxn<<2],l[18][maxn<<2],r[18][maxn<<2];//线段树
int Qmin(int x,int y,int d,int l0,int r0,int i)//求l0~r0 往下2^i层 最小值
{
if (l0>r0) return INF;
if (l0<=x&&y<=r0) return t[i][d];
int mid=(x+y)>>1;
if (r0<=mid) return Qmin(x,mid,d<<1,l0,r0,i);
if (l0>mid) return Qmin(mid+1,y,(d<<1)|1,l0,r0,i);
return min(Qmin(x,mid,d<<1,l0,mid,i),Qmin(mid+1,y,(d<<1)|1,mid+1,r0,i));
}
int Qmin_l(int x,int y,int d,int l0,int r0,int i)//求左端点的编号
{
if (l0>r0) return 500010;
if (l0<=x&&y<=r0) return l[i][d];
int mid=(x+y)>>1;
if (r0<=mid) return Qmin_l(x,mid,d<<1,l0,r0,i);
if (l0>mid) return Qmin_l(mid+1,y,(d<<1)|1,l0,r0,i);
return min(Qmin_l(x,mid,d<<1,l0,mid,i),Qmin_l(mid+1,y,(d<<1)|1,mid+1,r0,i));
}
int Qmax_r(int x,int y,int d,int l0,int r0,int i)//求右端点的编号
{
if (l0>r0) return -233;
if (l0<=x&&y<=r0) return r[i][d];
int mid=(x+y)>>1;
if (r0<=mid) return Qmax_r(x,mid,d<<1,l0,r0,i);
if (l0>mid) return Qmax_r(mid+1,y,(d<<1)|1,l0,r0,i);
return max(Qmax_r(x,mid,d<<1,l0,mid,i),Qmax_r(mid+1,y,(d<<1)|1,mid+1,r0,i));
}
void bt(int x,int y,int d) //建第0层的数
{
if (x==y)
{
t[0][d]=Min[x];
l[0][d]=L1[x];r[0][d]=R1[x];
return;
}
int mid=(x+y)>>1;
bt(x,mid,d<<1);
bt(mid+1,y,(d<<1)|1);
t[0][d]=min(t[0][d<<1],t[0][(d<<1)|1]);
l[0][d]=min(l[0][d<<1],l[0][(d<<1)|1]);
r[0][d]=max(r[0][d<<1],r[0][(d<<1)|1]);//下面的传上来
}
void built_tree(int x,int y,int d,int i)
{
if (x==y)
{
t[i][d]=min(t[i-1][d],Qmin(1,n,1,l[i-1][d],r[i-1][d],i-1));//倍增的搞法
l[i][d]=Qmin_l(1,n,1,l[i-1][d],r[i-1][d],i-1);
r[i][d]=Qmax_r(1,n,1,l[i-1][d],r[i-1][d],i-1);
return;
}
int mid=(x+y)>>1;
built_tree(x,mid,d<<1,i);
built_tree(mid+1,y,(d<<1)|1,i);
t[i][d]=min(t[i][d<<1],t[i][(d<<1)|1]);
l[i][d]=min(l[i][d<<1],l[i][(d<<1)|1]);
r[i][d]=max(r[i][d<<1],r[i][(d<<1)|1]);
}
int main()
{
n=read();root=read();
memset(Min,0x3f3f3f3f,sizeof(Min));
for (int i=1;i<=n;i++) a[i]=read();
for (int i=1;i<n;i++)
{
X=read();Y=read();
add(X,Y);add(Y,X);
}
l1=0;r1=1;q[1]=root;dfn[root]=1;vis[root]=1;
while (l1<r1)//bfs的预处理
{
l1++;
int x=q[l1],y=0;
Min[l1]=a[x];
L1[l1]=r1+1;
for (int i=po[x];i;i=ne[i])
{
y=to[i];if (vis[y]) continue;vis[y]=1;

r1++;q[r1]=y;
dfn[y]=r1;
}
R1[l1]=r1;
if (L1[l1]>R1[l1]) {L1[l1]=100000;R1[l1]=-1;}
}

bt(1,n,1);
for (int i=1;i<=17;i++) built_tree(1,n,1,i);
int Q=read();
int ans=0;
while (Q--)
{
X=read();Y=read();
X=(X+ans)%n+1;
Y=(Y+ans)%n;
ans=INF;
int ll=dfn[X],lr=dfn[X],ql,qr;
Y++;
for (int i=17;i>=0;i--)
{
if ((1<<i)&Y)
{
Y^=(1<<i);
ql=ll;qr=lr;
ans=min(ans,Qmin(1,n,1,ql,qr,i));
ll=Qmin_l(1,n,1,ql,qr,i);
lr=Qmax_r(1,n,1,ql,qr,i);
}
}
printf("%d\n",ans);
}
return 0;
}