Blackops

初心易得，始终难守

0%

CF Educational #33 题解

发表于 更新于 分类于 ，

A.Chess For Three

题意就是三个人不停地下棋，输了的那个人下去观战，观战的人上来和赢家继续下，按照时间顺序给定一系列的赢家和输家，问是否合法。
可以发现某一局的赢家只可能是上一局的观战者或者上一局的赢家，某一局的输家也只可能是上一局的观战者或者上一局的赢家，由于规定了第一局对战的两个人，因此每一局都可以由上一局的记录的到，那就用三个变量模拟记录一下每一局的三种人，看是否出现矛盾即可。

代码：

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
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 110;
int arr[N];

int main(void)
{
    int n, i;
    scanf("%d", &n);
    for (i = 1; i <= n; ++i)
        scanf("%d", &arr[i]);
    int flag = 1;
    if (arr[1] == 3)
        flag = 0;
    if (!flag)
        puts("NO");
    else
    {
        int win, lose, sp;
        if (arr[1] == 1)
        {
            win = 1;
            lose = 2;
            sp = 3;
        }
        else if (arr[1] == 2)
        {
            win = 2;
            lose  = 1;
            sp = 3;
        }
        for (i = 2; i <= n; ++i)
        {
            if (arr[i] == win)
            {
                win = win;
                lose = sp;
                sp = 6 - win - lose;
            }
            else if (arr[i] == sp)
            {
                lose = win;
                win = arr[i];
                sp = 6 - win - lose;
            }
            else
            {
                flag = 0;
                break;
            }
        }
        puts(flag ? "YES" : "NO");
    }
    return 0;
}

B.Beautiful Divisors

题意就是给你一个数找出这个数最大的美丽因数，由于美丽因数仅由低位的连续$k$个$0$加上高位的连续$k+1$个$1$组成，那么直接预处理出这些美丽因数，最多也就几十个吧，每次输入逆序找到第一个能被整除的因数就是答案了，当然答案是一定存在的因为$1$总是任意一个正整数的因数

代码：

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
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 1e5 + 7;
LL arr[N];

int main(void)
{
    int i;
    for (i = 0; i < 15; ++i)
    {
        LL one = 0;
        one = (1LL << (i + 1)) - 1LL;
        one <<= i;
        arr[i] = one;
    }
    LL n;
    while (cin >> n)
    {
        for (i = 14; i >= 0; --i)
        {
            if (n % arr[i] == 0)
            {
                printf("%I64d\n", arr[i]);
                break;
            }
        }
    }
    return 0;
}

C.Rumor

题意就是让你去传播言论，使得最终所有人都知道这个言论，每一个人要花一定价格才能让他去传播，但是一个人被传播之后会无偿地向它认识的人传播，因此可能只需要找到其中几个人传播就可以达到最终目的了，求最后的花费最小。很容易想到对这个朋友关系图求强连通分量，把每个$SCC$中花费最小的拿出来加到答案上即可，但是这个样子码量大。所以既然是无向图干嘛不考虑用并查集呢，把认识的人合并起来，最终一个集合就是代表了一个$SCC$，拿每一个点的花费去更新他所在集合的最小花费，最后把所有集合的最小花费加起来就是答案了。

代码:

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
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <bitset>
#include <string>
#include <stack>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 1e5 + 7;
int price[N], pre[N];
bool vis[N];

int Find(int n)
{
    return pre[n] == 0 ? n : pre[n] = Find(pre[n]);
}
void Merge(int a, int b)
{
    a = Find(a), b = Find(b);
    if (a != b)
        pre[a] = b;
}
int main(void)
{
    int n, m, a, b, i;
    scanf("%d%d", &n, &m);
    for (i = 1; i <= n; ++i)
        cin >> price[i];
    for (i = 0; i < m; ++i)
    {
        cin >> a >> b;
        Merge(a, b);
    }
    for (i = 1; i <= n; ++i)
    {
        int f = Find(i);
        price[f] = min(price[i], price[f]);
    }
    LL sum = 0;
    for (i = 1; i <= n; ++i)
    {
        int f = Find(i);
        if (vis[f])
            continue;
        sum += (LL)price[f];
        vis[f] = 1;
    }
    cout << sum << endl;
    return 0;
}

D.Credit Card

题意就是你有一张银行卡，有$N$天的晚间操作记录，如果操作记录大于$0$代表你向里面存款，小于$0$就是取款，等于$0$就是检查余额，要求是每当检查余额时存款不能为负数否则就输出$-1$，如果某一时刻存的钱大于$d$，也将输出$-1$，另外你在任意一天的早上可以直接去银行存任意多的钱，求尽量不出现$-1$时最少去银行存款的次数。显然任意一天的早上去存款实际上还不如在检查余额那天的早上去存款，然后考虑存款的影响， 假如我在第$x$天早上存款了$k$元，那么$[x,n]$天都会受到影响，即剩下那些天的余额一定会增加$k$，那么我只要在检查余额时如果发现余额为负数，那么一定要存款，贪心地存入对剩下的日子均没有影响的最大钱数，然后看这样存进去之后是不是还是负数，如果这天还是负数，说明只能输出$-1$，否则继续遍历更新，所以这里需要用线段树更新和查询区间的最大值。

代码：

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
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 1e5 + 7;
LL arr[N], pre[N];

struct seg
{
    int l, mid, r;
    LL mx, ad;
} T[N << 2];

void pushup(int k)
{
    T[k].mx = max(T[LC(k)].mx, T[RC(k)].mx);
}
void pushdown(int k)
{
    if (T[k].ad)
    {
        T[LC(k)].ad += T[k].ad;
        T[RC(k)].ad += T[k].ad;
        T[LC(k)].mx += T[k].ad;
        T[RC(k)].mx += T[k].ad;
        T[k].ad = 0;
    }
}
void build(int k, int l, int r)
{
    T[k].l = l;
    T[k].r = r;
    T[k].mid = MID(l, r);
    T[k].ad = 0;
    if (l == r)
        T[k].mx = pre[l];
    else
    {
        build(LC(k), l, T[k].mid);
        build(RC(k), T[k].mid + 1, r);
        pushup(k);
    }
}
void update(int k, int l, int r, LL v)
{
    if (l <= T[k].l && T[k].r <= r)
    {
        T[k].ad += v;
        T[k].mx += v;
    }
    else
    {
        pushdown(k);
        if (l <= T[k].mid)
            update(LC(k), l, r, v);
        if (r > T[k].mid)
            update(RC(k), l, r, v);
        pushup(k);
    }
}
LL query(int k, int l, int r)
{
    if (l <= T[k].l && T[k].r <= r)
        return T[k].mx;
    else
    {
        pushdown(k);
        if (r <= T[k].mid)
            return query(LC(k), l, r);
        else if (l > T[k].mid)
            return query(RC(k), l, r);
        else
            return max(query(LC(k), l, T[k].mid), query(RC(k), T[k].mid + 1, r));
    }
}
int main(void)
{
    int n, i;
    LL d;
    scanf("%d%I64d", &n, &d);
    for (i = 1; i <= n; ++i)
    {
        scanf("%I64d", &arr[i]);
        pre[i] = pre[i - 1] + arr[i];
        if (pre[i] > d)
            return puts("-1");
    }
    build(1, 1, n);
    int day = 0;
    for (i = 1; i <= n; ++i)
    {
        if (arr[i] == 0)
        {
            pre[i] = query(1, i, i);
            if (pre[i] < 0)
            {
                LL sufmax = query(1, i, n);
                LL delta = d - sufmax;
                update(1, i, n, delta);
                if (pre[i] + delta < 0)
                    return puts("-1");
                else
                    ++day;
            }
        }
    }
    printf("%d\n", day);
    return 0;
}

E.Counting Arrays

把一个数$x$恰好分解成$y$个数的乘积，问这样的$y$个数组成的序列有几种。由于是乘积的问题，我们可以先把$x$因数分解（准确的说应该叫质数分解），假设第$i$个因数为$a_i$，它在$x$中所占的指数为$b_i$，那么所要做的就是把这个$b_i$个$a_i$分到$y$个位置中去，问题就变成了将$b_i$个相同物品装入$y$的箱子，且允许出现空箱，那么这个因数$a_i$贡献的答案就是$C_{b_i+y-1}^{y-1}$（由于答案与补集的方案数等价，可以优化成$C_{b_i+y-1}^{b_i+y-1-(y-1)}=C_{b_i+y-1}^{b_i}$），那么把每一个因数按此方法求出来的方案数相乘就是$y$项全为正数的答案，但是题目说还可以用负数，那就是从$y$项中选出偶数项，在其前面添加负号，那这样的贡献就是$C_{y}^{0}+C_{y}^{2}+C_{y}^{4}+C_{y}^{6}$，即二项式展开的偶数项求和，用定理可以直接得到答案为$2^{y-1}$，最后再乘上这个数即可。注意过程中要即时取模，或者用快速乘法，否则很容易爆$long\ long$

树套树代码：

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
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 1e6 + 64 + 7;
const LL mod = 1e9 + 7;
LL fac[N];

inline LL qpow(LL a, LL b)
{
    LL r = 1;
    while (b)
    {
        if (b & 1)
            r = r * a % mod;
        a = a * a % mod;
        b >>= 1LL;
    }
    return r;
}
inline LL mul(LL a, LL b)
{
    LL r = 0;
    while (b)
    {
        if (b & 1)
            r = (r + a) % mod;
        a = (a + a) % mod;
        b >>= 1LL;
    }
    return r;
}
inline LL rev(LL x)
{
    return qpow(x, mod - 2LL);
}
inline LL C(int n, int m)
{
    return mul(mul(fac[n], rev(fac[m])), rev(fac[n - m]));
}
int main(void)
{
    fac[0] = 1;
    int i;
    for (i = 1; i < N; ++i)
        fac[i] = fac[i - 1] * (LL)i % mod;
    LL x, y;
    int TC;
    scanf("%d", &TC);
    while (TC--)
    {
        scanf("%I64d%I64d", &x, &y);
        LL ans = qpow(2LL, y - 1LL);
        for (LL i = 2; i * i <= x; ++i)
        {
            if (x % i == 0)
            {
                LL cnt = 0;
                while (x % i == 0)
                {
                    ++cnt;
                    x /= i;
                }
                ans = mul(ans, C(cnt + y - 1, cnt));
            }
        }
        if (x > 1)
            ans = mul(ans, y);
        printf("%I64d\n", ans);
    }
    return 0;
}

F.Subtree Minimum Query

题意就是给你一棵树，树边长度均为$1$，每个点均有权值，询问你某一个节点的子树中到这个节点的距离不超过$k$的这些节点集合中，最小权值是多少。询问强制在线
思路有一点，完全不知道代码如何实现，一开始用$BFS$、$DFS$序，（然后发现这样显然是错的），真的不会了……搜了波题解，发现原来是线段树套线段树（以前想学苦于智商太低想象力又不够好看不懂XD），然后就是照着人家的代码临摹一发，粗略地地理解一下，一维显然是按照$DFS$序开一个静态线段树，记这个静态线段树的下标为$p$p，以$root[p]$为根，按照节点的深度建立动态开点的线段树，最后询问就是查询一维在$[L[u], R[u]]$，二维在$[dep[u], dep[u] + k]$范围内的最小值。

早上起来突然发现如果我们用$DFS$序当第一维的关键字，到根节点的距离当第二维的关键字，当这玩意儿不就是个$KD-tree$的静态建树+二维矩阵最小值查询的模板题吗，而且空间复杂度才$O(n)$，赶紧码了一发，结果时间居然跟树套树几乎一样……只能说666了

树套树代码：

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 <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <bitset>
#include <string>
#include <stack>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 100010;
int n, rt, m, ans;

namespace G {
    vector<int>E[N];
    int L[N], R[N], ts;
    int ver[N], dis[N], val[N];
    inline void add(int s, int t)
    {
        E[s].push_back(t);
    }
    void dfs(int u, int f, const int &dep)
    {
        L[u] = ++ts;
        ver[ts] = u;
        dis[u] = dep;
        for (auto &v : E[u])
            if (v != f)
                dfs(v, u, dep + 1);
        R[u] = ts;
    }
}
namespace SG {
    struct seg
    {
        int ls, rs, v;
        void init(int _v)
        {
            ls = rs = 0;
            v = _v;
        }
    } T[10000010];
    int root[N << 2], sz;

    void update(int &k, int l, int r, int x, int v)
    {
        if (!k)
            T[k = ++sz].init(v);
        else
            T[k].v = min(T[k].v, v);
        if (l == r)
            return ;
        int mid = MID(l, r);
        if (x <= mid)
            update(T[k].ls, l, mid, x, v);
        else
            update(T[k].rs, mid + 1, r, x, v);
    }
    void build(int k, int l, int r, int pos, int x, int v)
    {
        update(root[k], 0, n - 1, x, v);
        if (l == r)
            return ;
        int mid = MID(l, r);
        if (pos <= mid)
            build(LC(k), l, mid, pos, x, v);
        else
            build(RC(k), mid + 1, r, pos, x, v);
    }
    int query(int k, int l, int r, int ql, int qr)
    {
        if (!k)
            return INF;
        if (ql <= l && r <= qr)
            return T[k].v;
        int mid = MID(l, r);
        if (qr <= mid)
            return query(T[k].ls, l, mid, ql, qr);
        else if (ql > mid)
            return query(T[k].rs, mid + 1, r, ql, qr);
        else
            return min(query(T[k].ls, l, mid, ql, mid), query(T[k].rs, mid + 1, r, mid + 1, qr));
    }
    void query(int k, int l, int r, int ql, int qr, int dl, int dr)
    {
        if (ql <= l && r <= qr)
            ans = min(ans, query(root[k], 0, n - 1, dl, dr));
        else
        {
            int mid = MID(l, r);
            if (qr <= mid)
                query(LC(k), l, mid, ql, qr, dl, dr);
            else if (ql > mid)
                query(RC(k), mid + 1, r, ql, qr, dl, dr);
            else
                query(LC(k), l, mid, ql, mid, dl, dr), query(RC(k), mid + 1, r, mid + 1, qr, dl, dr);
        }
    }
}
int main(void)
{
    int i;
    scanf("%d%d", &n, &rt);
    for (i = 1; i <= n; ++i)
        scanf("%d", &G::val[i]);
    for (i = 1; i < n; ++i)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        G::add(x, y);
        G::add(y, x);
    }
    G::dfs(rt, -1, 0);
    scanf("%d", &m);
    for (i = 1; i <= n; ++i)
    {
        int u = G::ver[i];
        SG::build(1, 1, n, i, G::dis[u], G::val[u]);
    }
    while (m--)
    {
        int x, k, p, q;
        scanf("%d%d", &p, &q);
        x = (p + ans) % n + 1;
        k = (q + ans) % n;
        ans = INF;
        SG::query(1, 1, n, G::L[x], G::R[x], G::dis[x], min(G::dis[x] + k, n - 1));
        printf("%d\n", ans);
    }
    return 0;
}

$KDtree$代码

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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <bitset>
#include <string>
#include <stack>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 100010;
int n, rt, m, ans;

namespace G {
    vector<int>E[N];
    int L[N], R[N], ts;
    int ver[N], dis[N], val[N];
    inline void add(int s, int t)
    {
        E[s].push_back(t);
    }
    void dfs(int u, int f, const int &dep)
    {
        L[u] = ++ts;
        ver[ts] = u;
        dis[u] = dep;
        for (auto &v : E[u])
            if (v != f)
                dfs(v, u, dep + 1);
        R[u] = ts;
    }
}
namespace SG {
    struct KD
    {
        int ls, rs;
        int d[2], mn[2], mx[2], v, Min;
        void init()
        {
            ls = rs = 0;
        }
    } T[N];
    int idx;
    struct info
    {
        int d[2], v;
        bool operator<(const info &rhs)const
        {
            return d[idx] < rhs.d[idx];
        }
    } node[N];
    int rt, sz, _x1, _y1, _x2, _y2;

    void init()
    {
        rt = sz = 0;
    }
    inline void pushup(int k)
    {
        int ls = T[k].ls, rs = T[k].rs;
        T[k].Min = T[k].v;
        if (ls)
        {
            for (int i = 0; i < 2; ++i)
            {
                T[k].mn[i] = min(T[k].mn[i], T[ls].mn[i]);
                T[k].mx[i] = max(T[k].mx[i], T[ls].mx[i]);
            }
            T[k].Min = min(T[k].Min, T[ls].Min);
        }
        if (rs)
        {
            for (int i = 0; i < 2; ++i)
            {
                T[k].mn[i] = min(T[k].mn[i], T[rs].mn[i]);
                T[k].mx[i] = max(T[k].mx[i], T[rs].mx[i]);
            }
            T[k].Min = min(T[k].Min, T[rs].Min);
        }
    }
    void build(int &k, int l, int r, int dim)
    {
        int mid = MID(l, r);
        idx = dim;
        nth_element(node + l, node + mid, node + r + 1);
        T[k = ++sz].init();
        for (int i = 0; i < 2; ++i)
            T[k].d[i] = T[k].mn[i] = T[k].mx[i] = node[mid].d[i];
        T[k].Min = T[k].v = node[mid].v;
        if (l < mid)
            build(T[k].ls, l, mid - 1, dim ^ 1);
        if (mid < r)
            build(T[k].rs, mid + 1, r, dim ^ 1);
        pushup(k);
    }
    inline bool inMat(int x, int y, int xx, int yy)
    {
        return _x1 <= x && xx <= _x2 && _y1 <= y && yy <= _y2;
    }
    inline bool outmat(int x, int y, int xx, int yy)
    {
        return _x2 < x || xx < _x1 || _y2 < y || yy < _y1;
    }
    int query(int k)
    {
        if (inMat(T[k].mn[0], T[k].mn[1], T[k].mx[0], T[k].mx[1]))
            return T[k].Min;
        else
        {
            int ret = INF;
            if (inMat(T[k].d[0], T[k].d[1], T[k].d[0], T[k].d[1]))
                ret = min(ret, T[k].v);
            int l = T[k].ls, r = T[k].rs;
            if (l && !outmat(T[l].mn[0], T[l].mn[1], T[l].mx[0], T[l].mx[1]))
                ret = min(ret, query(l));
            if (r && !outmat(T[r].mn[0], T[r].mn[1], T[r].mx[0], T[r].mx[1]))
                ret = min(ret, query(r));
            return ret;
        }
    }
}
int main(void)
{
    int i;
    scanf("%d%d", &n, &rt);
    for (i = 1; i <= n; ++i)
        scanf("%d", &G::val[i]);
    for (i = 1; i < n; ++i)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        G::add(x, y);
        G::add(y, x);
    }
    G::dfs(rt, -1, 0);
    for (i = 1; i <= n; ++i)
    {
        SG::node[i].d[0] = G::L[i];
        SG::node[i].d[1] = G::dis[i];
        SG::node[i].v = G::val[i];
    }
    SG::build(SG::rt, 1, n, 0);
    scanf("%d", &m);
    while (m--)
    {
        int x, k, p, q;
        scanf("%d%d", &p, &q);
        x = (p + ans) % n + 1;
        k = (q + ans) % n;
        SG::_x1 = G::L[x], SG::_x2 = G::R[x], SG::_y1 = G::dis[x], SG::_y2 = min(G::dis[x] + k, n - 1);
        printf("%d\n", ans = SG::query(SG::rt));
    }
    return 0;
}