CodeForces - 893 Educational Codeforces Round 33

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数： | 字数： 5.1k

CodeForces - 893 Educational Codeforces Round 33

1 A Chess For Three CodeForces - 893A

1.1 题目大意

A, B, C三个小伙伴玩象棋

象棋规则如下：

第一局A与B对弈，C观战

每一盘游戏结束后，输的小伙伴将观战，刚刚观战的小伙伴将与胜者继续对弈

他们共下了n盘象棋，并且记录下来了每一盘的胜者

请问记录是否有错（观战的人胜利即为出错）

1.2 解题思路

用 spec[] 数组 记录一下当前小伙伴们的状态（true为观战，false为对弈）

依次判断是否出现观战者胜利即可

胜者状态不变，败者与观战者的状态取反

1.3 代码实现

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <bits/stdc++.h>
using namespace std;
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d%d",&n,&m)
#define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", n, m)
#define sld(n) scanf("%lld",&n)
#define sldd(n,m) scanf("%lld%lld",&n,&m)
#define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define sf(n) scanf("%lf",&n)
#define sff(n,m) scanf("%lf%lf",&n,&m)
#define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)
#define ss(str) scanf("%s",str)
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define mm(a,n) memset(a, n, sizeof(a))
#define debug(x) cout<<#x<<": "<<x<<endl
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int maxn = 3e5 + 5;
//head
bool spec[5];
int main(){
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
    int n; sd(n);
    spec[3] = true;
    while(n--){
        int x; sd(x);
        if(spec[x]){
            puts("NO");
            return 0;
        }
        for(int i = 1; i <= 3; ++i){
            if(i == x) continue;
            spec[i] = !spec[i];
        }
    }
    puts("YES");
    return 0;
}

2 B - Beautiful Divisors CodeForces - 893B

2.1 题目大意

在二进制表示中，前面有$x$个1后面有$x-1$个0的数我们之称为美丽数

题目提示：

More formally, the number is beautiful iff there exists some positive integer k such that the number is equal to $(2^k - 1) * (2^{k - 1})$.

给定一个n，问它的最大美丽数因子是多少

2.2 解题思路

根据题意我们知道，第一个美丽数是1，第二个是6

第$k$个美丽数满足$(2^k - 1) * (2^{k - 1})$

因此，小于n的美丽数不会超过$log_2 n$个

因此我们枚举美丽数判定即可

2.3 代码实现

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <bits/stdc++.h>
using namespace std;
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d%d",&n,&m)
#define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", n, m)
#define sld(n) scanf("%lld",&n)
#define sldd(n,m) scanf("%lld%lld",&n,&m)
#define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define sf(n) scanf("%lf",&n)
#define sff(n,m) scanf("%lf%lf",&n,&m)
#define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)
#define ss(str) scanf("%s",str)
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define mm(a,n) memset(a, n, sizeof(a))
#define debug(x) cout<<#x<<": "<<x<<endl
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int maxn = 3e5 + 5;
//head
int getbn(int x){
    int ret = 1<<(2*x - 1);
    ret -= 1<<(x - 1);
    return ret;
}
int main(){
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
    int n; sd(n);
    int ans = 1;
    for(int i = 1; ; ++i){
        int x = getbn(i);
        if(x > n) break;
        if(n%x) continue;
        ans = x;
    }
    pd(ans);
    return 0;
}

3 C - Rumor CodeForces - 893C

3.1 题目大意

给定n个人

第$i$个人被贿赂需要$a_i$的代价

给定m个朋友关系

被贿赂的人会向他的朋友们免费传播谣言（当然，被贿赂的人已经算是被传播了谣言）

问这n个人都被传播谣言的最小代价是多少

3.2 解题思路

我们很容易知道

处于同一个朋友圈里的人，我们只需要贿赂这个朋友圈中所有人中代价最小的人

即可解决这个朋友圈

因此我们只需要并查集维护一下朋友圈以及朋友圈内的最小代价

然后枚举朋友圈，最小代价求和即是答案

3.3 代码实现

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <bits/stdc++.h>
using namespace std;
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d%d",&n,&m)
#define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", n, m)
#define sld(n) scanf("%lld",&n)
#define sldd(n,m) scanf("%lld%lld",&n,&m)
#define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define sf(n) scanf("%lf",&n)
#define sff(n,m) scanf("%lf%lf",&n,&m)
#define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)
#define ss(str) scanf("%s",str)
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define mm(a,n) memset(a, n, sizeof(a))
#define debug(x) cout<<#x<<": "<<x<<endl
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int maxn = 3e5 + 5;
//head
int fa[maxn];
ll cost[maxn];
int findfa(int x){
    int y = x;
    while(y != fa[y]) y = fa[y];
    while(x != fa[x]){
        int z = fa[x];
        fa[x] = y;
        x = z;
    }
    return y;
}
int main(){
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
    int n, m; sdd(n, m); 
    rep(i, 1, n + 1){
        sld(cost[i]);
        fa[i] = i;
    }
    while(m--){
        int x, y; sdd(x, y);
        int fx = findfa(x), fy = findfa(y);
        if(fx == fy) continue;
        cost[fy] = min(cost[fx], cost[fy]);
        fa[fx] = fy;
    }
    ll ans = 0;
    rep(i, 1, n + 1){
        if(fa[i] != i) continue;
        ans += cost[i];
    }
    pld(ans);
    return 0;
}

4 D - Credit Card CodeForces - 893D

4.1 题目大意

给定天数n，以及信用卡里的最大钱数d

每天晚上银行将会有一个操作$a_i$

如果$a_i == 0$ ，今天晚上将进行检查，如果信用卡里的钱数小于0，则信用卡将会被注销

如果$a_i > 0$，银行将在卡里充入$a_i$，否则将取走$a_i$

任何时刻卡里的钱数超过$d$元，信用卡将会被注销

你可以在每天早上去银行存钱（不可取钱）

问是否能够保证信用卡不被注销

可以的话，最少去银行存钱几次

4.2 解题思路

由于能够存钱，不能取钱

所以信用卡被注销，只有可能是因为信用卡里的钱超过了d元

因为在银行检查的当天，如果钱数小于零，在早上一定可以存钱使得其大于零

为了保证取得次数最少

我们在必须存钱时，一定是在保证在后续操作的钱数不超过d的情况下，存的越多越好

因此，我们只需要记录一下，在信用卡不被注销的情况下

当前可能的最大钱数是多少，当前可能的最小钱数是多少

当银行检查余额时

当前可能最小钱数如果小于零，则将置为0

当前可能最大钱数如果小于零则说明，我们必须进行一次存钱了，所以更新答案，将最大可能钱数置为 d

当银行进行存取钱操作时，更新最大最小钱数

如果最大钱数大于 d，则将其置回 d，保证满足题意

当当前可能的最小钱数大于d时，则信用卡一定会被注销

4.3 代码实现

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <bits/stdc++.h>
using namespace std;
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d%d",&n,&m)
#define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", n, m)
#define sld(n) scanf("%lld",&n)
#define sldd(n,m) scanf("%lld%lld",&n,&m)
#define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define sf(n) scanf("%lf",&n)
#define sff(n,m) scanf("%lf%lf",&n,&m)
#define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)
#define ss(str) scanf("%s",str)
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define mm(a,n) memset(a, n, sizeof(a))
#define debug(x) cout<<#x<<": "<<x<<endl
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int maxn = 3e5 + 5;
//head
int main(){
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
    int n, d; sdd(n, d);
    bool ok = true;
    int mx = 0, mi = 0, ans = 0;
    rep(i, 0, n){
        int x; sd(x);
        if(!ok) continue;
        if(x == 0){
            if(mx < 0){
                mx = d;
                ++ans;
            }
            if(mi < 0) mi = 0;
            continue;
        }
        mx += x, mi += x;
        if(x > 0){
            if(mx > d) mx = d;
            if(mi > d) ok = false;
        }
    }
    if(!ok) ans = -1;
    pd(ans);
    return 0;
}

5 E - Counting Arrays CodeForces - 893E

5.1 题目大意

q次询问

每次询问给定一个$x_i$和$y_i$

$y_i$个数的乘积为$x_i$的情况下，共用多少种排列情况

5.2 解题思路

我们将 $x$ 进行质因子分解

获得这样一种形式

这样的话，我们只需要考虑将每个特定的质因子分配给这$y$个数，一共有多少种情况

如果只能分配为正数时，总方案数将是这些质因子的方案数的乘积

加入某个质因子，它分解出来的个数是$cnt$个，将它们分配给$y$个数（允许分配零个）会有多少种情况呢

这样的话，相当于把$cnt$个球分配到$y$个桶里，允许空桶

使用隔板法的话，是不允许两个隔板之间的球的个数为零的

我们可以假设存在$cnt + y$个球，这样便可以使用隔板法后，每个桶里的球的个数 是 隔板间球的个数减一

即满足桶里球的个数可以为零，又满足使用隔板法的条件

这样的话，我们进行隔板法计算它的组合数将是

由于需要取模，所以需要预处理出来所有阶乘逆元

考虑负数的情况，由于给定的$x > 0$所以负数的个数将是偶数个

根据组合数的性质，所有奇数项的和等于所有偶数项的和，等于$tot = 2^{y - 1}$

因此最后的方案数需要乘上$tot$

由于直接暴力判定质因子，时间会超

所以我们考虑只枚举小于$sqrt(x)$的质因子

如果最后$x > 1$则说明x为一个素数

只需要乘上一个$C_y^1$也就是$y$即可

5.3 代码实现

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <bits/stdc++.h>
using namespace std;
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d%d",&n,&m)
#define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", n, m)
#define sld(n) scanf("%lld",&n)
#define sldd(n,m) scanf("%lld%lld",&n,&m)
#define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define sf(n) scanf("%lf",&n)
#define sff(n,m) scanf("%lf%lf",&n,&m)
#define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)
#define ss(str) scanf("%s",str)
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define mm(a,n) memset(a, n, sizeof(a))
#define debug(x) cout<<#x<<": "<<x<<endl
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int maxn = 3e5 + 5;
//head
const int mx = 3e6 + 5;
ll fac[mx], inv_fac[mx];
vector<int> p;
bool np[mx];
void getP(){
    np[1] = true;
    int sx = sqrt(mx);
    for(int i = 2; i < sx; ++i){
        if(!np[i]) p.pb(i);
        for(int j = 0; j < p.size(); ++j){
            int num = i*p[j];
            if(num >= sx) break;
            np[num] = true;
        }
    }
}
ll pow_m(ll a, ll b, ll mod){
    ll ret = 1;
    while(b){
        if(b&1) ret = (ret*a)%mod;
        a = (a*a)%mod;
        b >>= 1;
    }
    return ret;
}
void getFac(){
    fac[0] = 1;
    for(int i = 1; i < mx; ++i) fac[i] = (fac[i - 1]*i)%mod;
    inv_fac[mx - 1] = pow_m(fac[mx - 1], mod - 2, mod);
    for(int i = mx - 2; i >= 0; --i) inv_fac[i] = (inv_fac[i + 1]*(i + 1))%mod;
}
int main(){
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
    getFac();
    getP();
    int q; sd(q);
    int num = (int)p.size();
    while(q--){
        int x, y; sdd(x, y);
        ll ans = 1;
        rep(i, 0, num){
            if(x == 1) break;
            ll cnt = 0;
            while(x%p[i] == 0){
                ++cnt;
                x /= p[i];
            }
            if(cnt){
                ll val = fac[cnt + y - 1];
                val = (val*inv_fac[y - 1])%mod;
                val = (val*inv_fac[cnt])%mod;
                ans = (ans*val)%mod;
            }
        }
        if(x > 1) ans = (ans*(ll)y)%mod;
        ll val = pow_m(2LL, y - 1, mod);
        ans = (ans*val)%mod;
        pld(ans);
    }
    return 0;
}
/*


*/

6 F - Subtree Minimum Query CodeForces - 893F

6.1 题目大意

给定一棵n个节点以r为根的树，每个节点有一个权值 $a_i$

进行m次询问，每次询问以 x 为根节点， 距离不大于 k 的所有节点中，最小的权值是多少

询问强制在线（根据上次的答案解密下一次询问的 x 与 k）

6.2 解题思路

最多$10^5$个节点，$10^6$次询问，我们考虑使用线段树

由于有询问子树的需求，我们很容易想到获得这棵树的以r为根dfs序

在树的dfs序中，一棵树的子树部分，将会是连续的一个序列

因此我们便可以通过线段树来维护一些东西，搞一些事情

在重新审视题意，我们可以发现，假定dfs序列中以 x 为根的连续子序列是 $[lf, rt]$

要求距离 x 不超过 k, 因此在原树中，这些满足条件的节点深度在区间 $[d[x], d[x] + k]$ 中

因此我们所求的问题便转化为了，在二维坐标系中，在某个矩形区域内部点的最小权值

由于我们所求的最小值，没有可加减的性质，因此无法通过二维前缀和解决

这种情况下的解决办法有 kd树，树套树 等我还不会写的的神仙数据结构

因此我们继续审视题目，我们可以发现，在所给定的条件中

如果确定节点深度所在的区间，我们发现，它们的dfs序并没有什么特殊的性质

如果我们确定dfs序所在区间，我们可以发现，它们的深度一定大于$d[x]$（因为是以$x$为根节点的子树）

因此我们可以发现在深度 $[1, d[x])$ 中，没有任何节点处于其中

因此我们可以放心的将原问题转化为

在dfs序处于[lf, rt]，并且相对于原数深度不大于$d[x] + k$的节点中，最小权值是多少

我们发现在深度这个维度

我们不再需要截断某一段去查询（因为可以直接查询小于等于$d[x] + k$）的所有节点

这样的话，我们便不需要在考虑最小值无法加减截断的事情

因此我们便只需要以dfs序建一棵线段树，以深度（从小到大）为时间线推进维护起来即可

即，我们需要建一棵，以dfs序为基，以节点深度为时间轴的主席树（留坑，以后补一篇博客）即可

6.3 代码实现

1341ms 48700kB

主席树真好写 才花了3个小时就写完了

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <bits/stdc++.h>
using namespace std;
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d%d",&n,&m)
#define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", n, m)
#define sld(n) scanf("%lld",&n)
#define sldd(n,m) scanf("%lld%lld",&n,&m)
#define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define sf(n) scanf("%lf",&n)
#define sff(n,m) scanf("%lf%lf",&n,&m)
#define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)
#define ss(str) scanf("%s",str)
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define mm(a,n) memset(a, n, sizeof(a))
#define debug(x) cout<<#x<<": "<<x<<endl
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int mod = 1e9 + 7;
const double eps = 1e-9;
//head
const int maxn = 1e5 + 5;
struct node{
    int l, r;
    int mi;
}T[maxn<<5];
struct num{
    int id;
    int x, d;
    int lf, rt;
    bool operator <(const num& n) const{
        return d < n.d;
    }
}a[maxn];
int root[maxn], lst[maxn], cnt = 0;
void build(int& x, int l, int r){
    x = 0; T[x].mi = 0x3f3f3f3f;
    if(l == r) return ;
    int mid = (l + r)>>1;
    build(T[x].l, l, mid);
    build(T[x].r, mid + 1, r);
}
void update(int l, int r, int& x, int y, int pos, int val){
    T[++cnt] = T[y]; x = cnt;
    if(l == r){
        T[x].mi = val;
        return ;
    }
    int mid = (l + r)>>1;
    if(mid >= pos) update(l, mid, T[x].l, T[y].l, pos, val);
    else update(mid + 1, r, T[x].r, T[y].r, pos, val);
    T[x].mi = min(T[T[x].l].mi, T[T[x].r].mi);
}
int query(int l, int r, int x, int lf, int rt){
    int mid = (l + r)>>1, ret = 0x3f3f3f3f;
    if(lf <= l &&  rt >= r) return T[x].mi;
    if(lf <= mid) ret = min(ret, query(l, mid, T[x].l, lf, rt));
    if(rt > mid) ret = min(ret, query(mid + 1, r, T[x].r, lf, rt));
    return ret;
}
vector<int> g[maxn];
void addedge(int u, int v){
    g[u].pb(v);
    g[v].pb(u);
}
int mx = 0;
void dfs(int now, int lst){
    if(mx < a[now].d) mx = a[now].d; 
    int sz = g[now].size();
    a[now].lf = ++cnt;
    rep(i, 0, sz){
        int to = g[now][i];
        if(lst == to) continue;
        a[to].d = a[now].d + 1; dfs(to, now);
    }
    a[now].rt = cnt;
}
bool cmp(num a, num b){
    return a.id < b.id;
}
int main(){
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
    int n, r; sdd(n, r);
    rep(i, 1, n + 1){
        sd(a[i].x);
        a[i].id = i; 
    }
    build(root[0], 1, n);
    rep(i, 1, n){
        int x, y; sdd(x, y);
        addedge(x, y);
    }
//    puts("");
    a[r].d = 1; dfs(r, -1);
//    rep(i, 0, n){
//        printf("%d %d %d", i, a[i].lf, a[i].rt);
//        printf(" %d\n", a[i].d);
//    }
    sort(a + 1, a + n + 1);
    rep(i, 1, n + 1) update(1, n, root[i], root[i - 1], a[i].lf, a[i].x);
    for(int i = 1; i <= n; ++i){
        int pos = i;
        while(pos < n){
            if(a[i].d != a[pos + 1].d) break;
            ++pos;
        }
        lst[a[i].d] = pos;
        i = pos;
    }
    sort(a + 1, a + n + 1, cmp);
    int ans = 0, m; sd(m);
    while(m--){
        int p, q; sdd(p, q);
        p = (ans + p)%n + 1, q = (ans + q)%n;
        int dd = min(mx, a[p].d + q);
        ans = query(1, n, root[lst[dd]], a[p].lf, a[p].rt);
        pd(ans);
    }
    return 0;
}