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 <algorithm>
const int MAXN = 20005;
const int MAXN_LOG = 20;
const int MAXL = 63;
struct {
long long a[MAXL + 1];
LinearBasic() {
std::fill(a, a + MAXL + 1, 0);
}
void insert(long long t) {
for (int i = MAXL; ~i; i--) {
if (!t) return;
if (!(t & (1ll << i))) continue;
if (a[i]) t ^= a[i];
else {
for (int j = 0; j < i; j++) if (t & (1ll << j)) t ^= a[j];
for (int j = i + 1; j <= MAXL; j++) if (a[j] & (1ll << i)) a[j] ^= t;
a[i] = t;
return;
}
}
}
long long queryMax() {
long long res = 0;
for (int i = 0; i <= MAXL; i++) res ^= a[i];
return res;
}
void merge(const LinearBasic &another) {
for (int i = 0; i <= MAXL; i++) insert(another.a[i]);
}
friend LinearBasic merge(const LinearBasic &a, const LinearBasic &b) {
LinearBasic res = a;
for (int i = 0; i <= MAXL; i++) res.insert(b.a[i]);
return res;
}
};
struct Edge;
struct Node {
Edge *e;
Node *f[MAXN_LOG];
LinearBasic lb[MAXN_LOG];
int dep;
long long val;
} N[MAXN];
struct Edge {
Node *u, *v;
Edge *next;
Edge() {}
Edge(Node *u, Node *v) : u(u), v(v), next(u->e) {}
} _pool[MAXN << 1], *_curr = _pool;
void addEdge(int u, int v) {
N[u].e = new (_curr++) Edge(&N[u], &N[v]);
N[v].e = new (_curr++) Edge(&N[v], &N[u]);
}
void dfs(Node *u, bool init = false) {
if (init) {
u->f[0] = u;
u->dep = 1;
u->lb[0].insert(u->val);
}
for (int i = 1; i < MAXN_LOG; i++) {
u->f[i] = u->f[i - 1]->f[i - 1];
u->lb[i] = merge(u->lb[i - 1], u->f[i - 1]->lb[i - 1]);
}
for (Edge *e = u->e; e; e = e->next) if (e->v != u->f[0]) {
e->v->f[0] = u;
e->v->lb[0].insert(u->val);
e->v->dep = u->dep + 1;
dfs(e->v);
}
}
LinearBasic lca(Node *u, Node *v) {
if (u->dep < v->dep) std::swap(u, v);
LinearBasic res;
res.insert(u->val), res.insert(v->val);
for (int i = MAXN_LOG - 1; ~i; i--) {
if (u->f[i]->dep >= v->dep) {
res.merge(u->lb[i]);
u = u->f[i];
}
}
if (u == v) return res;
for (int i = MAXN_LOG - 1; ~i; i--) {
if (u->f[i] != v->f[i]) {
res.merge(merge(u->lb[i], v->lb[i]));
u = u->f[i];
v = v->f[i];
}
}
res.insert(u->f[0]->val);
return res;
}
int main() {
int n, q;
scanf("%d %d", &n, &q);
for (int i = 1; i <= n; i++) scanf("%lld", &N[i].val);
for (int i = 1; i < n; i++) {
int u, v;
scanf("%d %d", &u, &v);
addEdge(u, v);
}
dfs(&N[1], true);
while (q--) {
int u, v;
scanf("%d %d", &u, &v);
printf("%lldn", lca(&N[u], &N[v]).queryMax());
}
return 0;
}
|
近期评论