题意
题目链接
Sol
线性基是可以合并的
倍增维护一下
然后就做完了？？
喵喵喵？
代码语言：javascript复制// luogu-judger-enable-o2
#include<bits/stdc .h>
#define LL long long
using namespace std;
const int MAXN = 2e4 10, B = 60;
inline LL read() {
char c = getchar(); LL x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 c - '0', c = getchar();
return x * f;
}
int N, Q, g[MAXN][16], dep[MAXN];
LL a[MAXN];
vector<int> v[MAXN];
struct Node {
LL P[62];
Node() {
memset(P, 0, sizeof(P));
}
void insert(LL x) {
for(int i = B; i >= 0; i--) {
if((!(x >> i & 1))) continue;
if(P[i]) {x ^= P[i]; continue;}
P[i] = x; break;
}
}
LL QueryMax() {
LL ans = 0;
for(int i = B; i >= 0; i--) ans = max(ans, ans ^ P[i]);
return ans;
}
Node operator (const Node &rhs) const {
Node ans;
for(int i = 0; i <= B; i ) ans.P[i] = this -> P[i];
for(int i = 0; i <= B; i ) if(rhs.P[i]) ans.insert(rhs.P[i]);
return ans;
}
}f[MAXN][16];
void dfs(int x, int fa) {
dep[x] = dep[fa] 1;
g[x][0] = fa;
f[x][0].insert(a[x]); f[x][0].insert(a[fa]);
for(int i = 0; i < v[x].size(); i ) {
int to = v[x][i];
if(to == fa) continue;
dfs(to, x);
}
}
void Pre() {
for(int j = 1; j <= 15; j )
for(int i = 1; i <= N; i )
g[i][j] = g[g[i][j - 1]][j - 1],
f[i][j] = f[i][j - 1] f[g[i][j - 1]][j - 1];
}
LL Query(int x, int y) {
Node base; base.insert(a[x]); base.insert(a[y]);
if(dep[x] < dep[y]) swap(x, y);
for(int i = 15; i >= 0; i--)
if(dep[g[x][i]] >= dep[y])
base = base f[x][i], x = g[x][i];
if(x == y) return base.QueryMax();
for(int i = 15; i >= 0; i--)
if(g[x][i] != g[y][i]) {
base = base f[x][i];
base = base f[y][i];
x = g[x][i], y = g[y][i];
}
base = base f[x][0]; base = base f[y][0];
return base.QueryMax();
}
int main() {
#ifndef ONLINE_JUDGE
//freopen("a.in", "r", stdin); freopen("b.out", "w", stdout);
#endif
N = read(); Q = read();
for(int i = 1; i <= N; i ) a[i] = read();
for(int i = 1; i <= N - 1; i ) {
int x = read(), y = read();
v[x].push_back(y); v[y].push_back(x);
}
dfs(1, 0);
Pre();
while(Q--) {
int x = read(), y = read();
printf("%lldn", Query(x, y));
}
return 0;
}
/*
8 4
45654 251 321 54687 321321 654 6321432 5646
1 2
2 3
2 4
1 5
4 6
6 7
5 8
7 8
7 5
6 8
4 1
*/
