https://www.luogu.com.cn/problem/P3292
多次询问求一条链取若干点的最大异或和
考虑一个集合的最大异或和可以求出线性基完成，两个集合的线性基可以合并，但是线性基并没有可减性，于是我们求 lca 的时候只能每次往集合里添加一条链，为了保证复杂度只能用倍增做。
std::vector<i64> merge(std::vector<i64> a, std::vector<i64> b) {
std::vector<i64> c = a;
for (int i = 60; i >= 0; i--) {
i64 t = b[i];
for (int j = 60; j >= 0; j--) {
if (!t) break; if ((t >> j & 1) == 0) continue;
if (!c[j]) c[j] = t; t ^= c[j];
}
}
return c;
}
int main() {
int n = read(), Q = read(); i64 val[n + 1];
std::vector<int> edge[n + 1];
for (int i = 1; i <= n; i++) val[i] = read();
edge[1].push_back(0);
for (int i = 1; i < n; i++) {
int u = read(), v = read();
edge[u].push_back(v); edge[v].push_back(u);
}
int fa[n + 1][20] = {0}, dep[n + 1] = {0};
std::vector<i64> box[n + 1][20];
std::function<void(int, int)> dfs = [&](int u, int last) -> void {
dep[u] = dep[last] + 1;
for (auto v : edge[u]) {
if (v == last) {
fa[u][0] = v; box[u][0].resize(61);
for (int j = 60; j >= 0; j--) {
if ((val[u] >> j & 1) == 0) {box[u][0][j] = val[u]; break;}
}
for (int j = 1; j <= 18; j++) {
int F = fa[u][j - 1];
if (!F || !fa[F][j - 1]) break;
fa[u][j] = fa[F][j - 1];
box[u][j] = merge(box[u][j - 1], box[F][j - 1]);
}
break;
}
}
for (auto v : edge[u]) {
if (v == last) continue; dfs(v, u);
}
};
dfs(1, 0);
while (Q--) {
std::vector<i64> boxx(61, 0);
int x = read(), y = read();
if (dep[x] < dep[y]) std::swap(x, y);
int t = dep[x] - dep[y], p = 0;
while (t) {
if (t & 1) {
boxx = merge(boxx, box[x][p]); x = fa[x][p];
}
t >>= 1; p++;
}
if (x != y) {
for (int i = 18; i >= 0; i--) {
if (fa[x][i] == fa[y][i]) continue;
boxx = merge(boxx, box[x][i]);
boxx = merge(boxx, box[y][i]);
x = fa[x][i]; y = fa[y][i];
}
boxx = merge(boxx, box[x][0]);
boxx = merge(boxx, box[y][0]);
x = fa[x][0];
}
boxx = merge(boxx, box[x][0]);
i64 ans = 0;
for (int i = 60; i >= 0; i--) {
ans = std::max(ans, ans ^ boxx[i]);
}
printf("%lld\n", ans);
}
}