link
Description
给定一棵 \(n\) 个节点的树，每个节点有一个正整数权值 \(w_i\)。
进行 \(q\) 次询问，每次询问给出两个节点 \(x, y\)，从 \(x\) 到 \(y\) 路径上的所有节点的权值中选出若干个数（可以不选），使得它们的异或和最大，输出这个最大值。
\(1 \le n \le 2 \times 10^4\)，\(1 \le m \le 2 \times 10^5\)，\(1 \le w_i \le 2^{60}\)。
Solution
异或和最大，容易想到线性基。
线性基是根据序列生成的具有如下特殊性质的一个集合：
- 在该集合中任选一些数的异或和，等于原序列中任选一些数的异或和；
- 满足上述条件的极小集合。
因此线性基有如下附加性质：
- 原序列中的任何数，都等于线性基中任选一些数的异或和；
- 线性基中不存在一组数，使得它们的异或和为 \(0\)；
- 线性基中不存在两组取值集合，使得它们的异或值相等。
（思考：为什么？）
于是我们可以写出线性基的封装结构：
struct LB {int bss[MaxBit + 5];LB() { memset(bss, 0, sizeof(bss)); }void insert(int x) {for (int j = MaxBit; ~j; j--) {if (!(x & (1ll << j))) continue;if (bss[j]) x ^= bss[j];else { bss[j] = x; break; }}}void unite(LB y) {for (int j = MaxBit; ~j; j--) {if (y.bss[j]) insert(y.bss[j]);}}int query() {int res = 0;for (int j = MaxBit; ~j; j--) {if ((res ^ bss[j]) > res) res ^= bss[j];}return res;}
};
-
bss数组线性基集合。
bss[j]表示最高位为j的基。 -
insert方法向线性基中插入一个数。
原理：不断地用既有的线性基去攻击它，直到它剩下一些不可消除的数。这些数于是成为新的线性基。
-
unite方法合并两个线性基。
基于暴力合并，因此单次时间复杂度为 \(O(\log^2 V)\)。
-
query方法查询线性基中，异或和的最大值。
考虑将树上问题转换为链上问题，注意到树上两点间路径最多仅能转化为两条链，因此对这两条链分别处理。用树上倍增预处理每个节点往上走 \(2^j\) 步的路径上所有节点权值的线性基。查询时，将 \(u \leftrightarrow v\) 的路径拆分成 \(u \leftrightarrow \text{LCA}(u, v)\) 和 \(v \leftrightarrow \text{LCA}(u, v)\)，将这些段的线性基合并，最后求最大异或和。
写法注意：以 LCA 模板为基础，边倍增边更新线性基。
代码：
#include <bits/stdc++.h>
#define int long long
#define inf 1e18
#define debug cout << '!';
#define filein(x) freopen(#x".in", "r", stdin);
#define fileout(x) freopen(#x".out", "w", stdout);
#define file(x) filein(x) fileout(x)
// #define Fast_IO
using namespace std;
#ifdef Fast_IO
inline int read() {int x = 0, f = 1; char c = getchar();while (c < '0' or c > '9') { if (c == '-') f = -1; c = getchar(); }while (c >= '0' and c <= '9') { x = x * 10 + c - '0'; c = getchar(); }return x * f;
}
void write(int x) {if (x < 0) putchar('-'), x = -x;if (x > 9) write(x / 10);putchar(x % 10 + '0'); return;
}
#endif
const int MaxN = 2e4, MaxL = 15, MaxBit = 62;
int n, q;
int anc[MaxN + 5][MaxL + 5], dep[MaxN + 5], val[MaxN + 5];
struct LB {int bss[MaxBit + 5];LB() { memset(bss, 0, sizeof(bss)); }void insert(int x) {for (int j = MaxBit; ~j; j--) {if (!(x & (1ll << j))) continue;if (bss[j]) x ^= bss[j];else { bss[j] = x; break; }}}void unite(LB y) {for (int j = MaxBit; ~j; j--) {if (y.bss[j]) insert(y.bss[j]);}}int query() {int res = 0;for (int j = MaxBit; ~j; j--) {if ((res ^ bss[j]) > res) res ^= bss[j];}return res;}
} lb[MaxN + 5][MaxL + 5];
vector<int> g[MaxN + 5];
void DFS(int u, int fa) {lb[u][0].insert(val[u]);for (auto v: g[u]) {if (v == fa) continue;dep[v] = dep[u] + 1;anc[v][0] = u;DFS(v, u);}
}
void LCA_init() {for (int j = 1; j <= MaxL; j++) {for (int i = 1; i <= n; i++) {anc[i][j] = anc[anc[i][j - 1]][j - 1];lb[i][j] = lb[i][j - 1];lb[i][j].unite(lb[anc[i][j - 1]][j - 1]);}}
}
int LCA_query(int u, int v) {LB cur;if (dep[u] < dep[v]) swap(u, v);for (int j = MaxL; ~j; j--) {if (dep[anc[u][j]] >= dep[v]) {cur.unite(lb[u][j]);u = anc[u][j];}}if (u == v) {cur.insert(val[u]);return cur.query();}for (int j = MaxL; ~j; j--) {if (anc[u][j] != anc[v][j]) {cur.unite(lb[u][j]), cur.unite(lb[v][j]);u = anc[u][j], v = anc[v][j];}}cur.unite(lb[u][0]), cur.unite(lb[v][0]);cur.insert(val[anc[u][0]]);return cur.query();
}
signed main() {cin.tie(0) -> sync_with_stdio(0);cin >> n >> q;for (int i = 1; i <= n; i++) {cin >> val[i];}for (int i = 1; i < n; i++) {int u, v; cin >> u >> v;g[u].push_back(v); g[v].push_back(u);}DFS(1, 0);LCA_init();while (q--) {int u, v; cin >> u >> v;cout << LCA_query(u, v) << '\n';}return 0;
}