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
| #pragma GCC optimize("inline")
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e+5 + 5;
struct edge {
int to, nxt;
}e[maxn << 1];
int ptr, lnk[maxn], tot;
int n, q, dfn[maxn], siz[maxn], top[maxn], dep[maxn];
int cnt, mxson[maxn], v[maxn], w[maxn], fa[maxn];
int tr[maxn * 35][2], s[maxn * 35], mx, mxbit, id[maxn];
inline int rd() {
register int x = 0, c = getchar();
while (!isdigit(c)) c = getchar();
while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
return x;
}
inline void add(int bgn, int end) {
e[++ptr] = (edge){end, lnk[bgn]};
lnk[bgn] = ptr;
}
void dfs(int x, int f) {
fa[x] = f;
dep[x] = dep[f] + 1;
siz[x] = 1;
for (int p = lnk[x]; p; p = e[p].nxt) {
int y = e[p].to;
if (y == f) continue;
dfs(y, x);
siz[x] += siz[y];
if (siz[y] > siz[mxson[x]]) mxson[x] = y;
}
}
void dfs2(int x, int init) {
top[x] = init;
dfn[x] = ++cnt;
w[cnt] = v[x];
if (!mxson[x]) return;
dfs2(mxson[x], init);
for (int p = lnk[x]; p; p = e[p].nxt) {
int y = e[p].to;
if (y == fa[x] || y == mxson[x]) continue;
dfs2(y, y);
}
}
void update(int &x, int cur, int p, int d) {
x = ++tot;
tr[x][0] = tr[cur][0]; tr[x][1] = tr[cur][1]; s[x] = s[cur] + 1;
if (!~d) return;
update(tr[x][(p >> d) & 1], tr[cur][(p >> d) & 1], p, d - 1);
}
int query(int x, int cur, int p, int d) {
if (!~d) return 0;
int curb = (p >> d) & 1, ch = curb ^ 1;
if (s[tr[x][ch]] - s[tr[cur][ch]])
return query(tr[x][ch], tr[cur][ch], p, d - 1) | (1 << d);
ch ^= 1;
return query(tr[x][ch], tr[cur][ch], p, d - 1);
}
inline int queryt(int x, int y, int z) {
int ret = 0;
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) swap(x, y);
ret = max(ret, query(id[dfn[x]], id[dfn[top[x]] - 1], z, mxbit));
x = fa[top[x]];
}
if (dep[x] > dep[y]) swap(x, y);
ret = max(ret, query(id[dfn[y]], id[dfn[x] - 1], z, mxbit));
return ret;
}
int main() {
n = rd(); q = rd();
for (int i = 1; i <= n; ++i)
v[i] = rd(), mx = max(mx, v[i]);
while ((1 << mxbit) < mx) mxbit++;
mxbit--;
int u, v;
for (int i = 1; i < n; ++i) {
u = rd(); v = rd();
add(u, v);
add(v, u);
}
dfs(1, 0);
dfs2(1, 1);
for (int i = 1; i <= n; ++i) update(id[i], id[i - 1], w[i], mxbit);
int opt, x, y, z;
while (q--) {
opt = rd();
if (opt == 1) {
x = rd(); y = rd();
printf("%d\n", query(id[dfn[x] + siz[x] - 1], id[dfn[x] - 1], y, mxbit));
} else {
x = rd(); y = rd(); z = rd();
printf("%d\n", queryt(x, y, z));
}
}
return 0;
}
|
