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
|
#include <bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &a){
T w=1; a=0;
char ch=getchar();
for(;ch < '0' || ch > '9';ch=getchar()) if(ch == '-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) a=(a<<3)+(a<<1)+(ch^48);
a*=w;
}
template <typename T> inline void ckmax(T &a, T b){a = a > b ? a : b;}
template <typename T> inline void ckmin(T &a, T b){a = a < b ? a : b;}
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mii map<int, int>
#define pii pair<int, int>
#define vi vector<int>
#define Debug(x) cout << #x << " = " << x << endl
#define For(i,l,r) for (int i = l; i <= r; ++i)
#define foR(i,l,r) for (int i = l; i >= r; --i)
const int N = 5e4 + 10;
struct edge {
int to, nxt;
} e[N << 1];
int head[N], cnt;
inline void add (int u, int v) {
e[++cnt].to = v; e[cnt].nxt = head[u]; head[u] = cnt;
}
int dp[N][32], dep[N];
void dfs (int u, int fa) {
dep[u] = dep[fa] + 1, dp[u][0] = fa;
for (int i = 1; (1 << i) <= dep[u]; ++i)
dp[u][i] = dp[dp[u][i - 1]][i - 1];
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (v == fa) continue;
dfs (v, u);
}
}
int n, q;
int a[N];
struct Trie {
int ch[2048][2], tot, rt;
inline void clear () {
memset (ch, 0, sizeof ch);
tot = 1; rt = 1;
}
inline void ins (int x) {
int cur = rt;
foR (i, 7, 0) {
int p = (x >> i) & 1;
if (!ch[cur][p]) ch[cur][p] = ++tot;
cur = ch[cur][p];
}
}
int que (int x) {
int Ans = 0, cur = rt;
foR (i, 7, 0) {
int p = (x >> i) & 1;
if (ch[cur][!p]) Ans |= (1 << i), cur = ch[cur][!p];
else cur = ch[cur][p];
}
return Ans;
}
} tr;
const int B = 256;
int mxp[260], mx[N][260];
int main() {
read(n); read(q);
For (i, 1, n) read(a[i]);
For (i, 1, n - 1) {
int u, v; read(u); read(v); add(u, v); add(v, u);
}
dfs (1, 0);
For (i, 1, n) {
tr.clear();
memset (mxp, 0, sizeof mxp);
for (int j = i, st = 0; j && st < B; j = dp[j][0], st++) {
ckmax(mxp[a[j] >> 8], st ^ (a[j] & (B - 1)));
tr.ins(a[j] >> 8);
}
For (j, 0, B - 1) {
int p = tr.que(j);
ckmax(mx[i][j], (p << 8) | mxp[p ^ j]);
}
}
For (i, 1, q) {
int u, v; read(u); read(v);
int cur = v, st = 0, Ans = 0;
while (dep[cur] - dep[u] >= B) ckmax(Ans, mx[cur][st]), st++, cur = dp[cur][8];
while (cur ^ u) ckmax(Ans, a[cur] ^ (dep[v] - dep[cur])), cur = dp[cur][0];
ckmax(Ans, a[u] ^ (dep[v] - dep[u]));
printf ("%d\n", Ans);
}
}
|
