「BZOJ4568」[SCOI2016]幸运数字

Description

A 国共有nn座城市,这些城市由n1n - 1条道路相连,使得任意两座城市可以互达,且路径唯一。每座城市都有一个幸运数字,以纪念碑的形式矗立在这座城市的正中心,作为城市的象征。一些旅行者希望游览 A 国。旅行者计划乘飞机降落在xx号城市,沿着xx号城市到yy号城市之间那条唯一的路径游览,最终从yy城市起飞离开 A 国。

在经过每一座城市时,游览者就会有机会与这座城市的幸运数字拍照,从而将这份幸运保存到自己身上。然而,幸运是不能简单叠加的,这一点游览者也十分清楚。他们迷信着幸运数字是以异或的方式保留在自己身上的。例如,游览者拍了33张照片,幸运值分别是55771111,那么最终保留在自己身上的幸运值就是995xor7xor115 \mathbin{\text{xor}} 7 \mathbin{\text{xor}} 11)。

有些聪明的游览者发现,只要选择性地进行拍照,便能获得更大的幸运值。例如在上述三个幸运值中,只选择551111,可以保留的幸运值为1414。现在,一些游览者找到了聪明的你,希望你帮他们计算出在他们的行程安排中可以保留的最大幸运值是多少。

Input

第一行包含两个正整数nnqq,分别表示城市的数量和旅行者数量。
第二行包含nn个非负整数,其中第ii个整数GiG_i表示ii号城市的幸运值。随后n1n - 1行,每行包含两个正整数xxyy,表示xx号城市和yy号城市之间有一条道路相连。
随后qq行,每行包含两个正整数xxyy,表示这名旅行者的旅行计划是从xx号城市到yy号城市。

Output

输出需要包含 qq 行,每行包含 11 个非负整数,表示这名旅行者可以保留的最大幸运值。

Sample Input

1
2
3
4
5
6
7
4 2
11 5 7 9
1 2
1 3
1 4
2 3
1 4

Sample Output

1
2
14
11

HINT

N20000,Q200000,Gi260N \leq 20000, Q \leq 200000, G_i \leq 2 ^ {60}

Solution

异或和最大\Leftrightarrow线性基
在求LCALCA的时候暴力合并线性基,然后贪心求答案。

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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 21000;
int n, Q;
ll a[N];
struct Edge {
int u, v, nxt;
}e[N * 2];
int head[N], en;
void addedge(int x, int y) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en;
}
int f[N][21], d[N];
ll g[N][21][61];
void ins(ll *a, ll val) {
for(int i = 60; ~i; --i)
if(val & (1ll << i)) {
if(!a[i]) {
a[i] = val;
break;
}
val ^= a[i];
}
}
void merge(ll *a, ll *b) {
for(int i = 60; ~i; --i)
if(b[i]) ins(a, b[i]);
}
void dfs(int x, int F) {
f[x][0] = F;
ins(g[x][0], a[F]);
d[x] = d[F] + 1;
for(int i = 1; i <= 20; ++i) {
f[x][i] = f[f[x][i - 1]][i - 1];
merge(g[x][i], g[f[x][i - 1]][i - 1]);
merge(g[x][i], g[x][i - 1]);
}
for(int i = head[x]; i; i = e[i].nxt) {
int y = e[i].v;
if(y == F) continue;
dfs(y, x);
}
}
ll cal(ll *a) {
ll ans = 0;
for(int i = 60; ~i; --i)
if((ans ^ a[i]) > ans) ans ^= a[i];
return ans;
}
ll solve(int x, int y) {
if(x == y) return a[x];
ll ans[61] = {0};
ins(ans, a[x]);
ins(ans, a[y]);
if(d[x] < d[y]) swap(x, y);
for(int i = 20; ~i; --i)
if(d[f[x][i]] >= d[y]) merge(ans, g[x][i]), x = f[x][i];
if(x == y) return cal(ans);
for(int i = 20; ~i; --i) if(f[x][i] != f[y][i]) {
merge(ans, g[x][i]);
merge(ans, g[y][i]);
x = f[x][i];
y = f[y][i];
}
merge(ans, g[x][0]);
return cal(ans);
}
int main() {
n = read(), Q = read();
for(int i = 1; i <= n; ++i) a[i] = read();
for(int i = 1; i < n; ++i) {
int x = read(), y = read();
addedge(x, y);
addedge(y, x);
}
dfs(1, 1);
while(Q--) {
int x = read(), y = read();
writeln(solve(x, y));
}
return 0;
}