AC题解

用带深度标记的线性基在树上预处理后，每次查询只需提取路径两端点线性基中深度不低于最近公共祖先的部分，合并后贪心求最大值即可。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 20005;
const int LOG = 15;
const int BIT = 60;

int n, q;
long long val[MAXN];
vector<int> g[MAXN];

// 倍增求LCA
int fa[MAXN][LOG + 1], dep[MAXN];

// 每个节点的线性基，b[u][i] 为基元素，d[u][i] 为其深度（最深节点）
long long b[MAXN][BIT + 1];
int d[MAXN][BIT + 1];

void dfs(int u, int par) {
    fa[u][0] = par;
    dep[u] = dep[par] + 1;
    for (int i = 1; i <= LOG; i++)
        fa[u][i] = fa[fa[u][i-1]][i-1];
    
    // 复制父亲的线性基
    if (par != 0) {
        memcpy(b[u], b[par], sizeof(b[u]));
        memcpy(d[u], d[par], sizeof(d[u]));
    } else {
        memset(b[u], 0, sizeof(b[u]));
        memset(d[u], 0, sizeof(d[u]));
    }
    
    // 插入当前节点的值 (带深度)
    long long cur = val[u];
    int curd = dep[u];
    for (int i = BIT; i >= 0; i--) {
        if ((cur >> i) & 1) {
            if (!b[u][i]) {
                b[u][i] = cur;
                d[u][i] = curd;
                break;
            }
            if (d[u][i] < curd) {
                swap(cur, b[u][i]);
                swap(curd, d[u][i]);
            }
            cur ^= b[u][i];
        }
    }
    
    for (int v : g[u]) if (v != par) dfs(v, u);
}

int lca(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    for (int i = LOG; i >= 0; i--)
        if (dep[x] - (1 << i) >= dep[y])
            x = fa[x][i];
    if (x == y) return x;
    for (int i = LOG; i >= 0; i--)
        if (fa[x][i] != fa[y][i])
            x = fa[x][i], y = fa[y][i];
    return fa[x][0];
}

long long query(int x, int y) {
    int w = lca(x, y);
    long long tmp[BIT + 1] = {0};
    
    // 插入函数（普通线性基）
    auto insert = [&](long long val) {
        for (int i = BIT; i >= 0; i--) {
            if ((val >> i) & 1) {
                if (!tmp[i]) {
                    tmp[i] = val;
                    break;
                }
                val ^= tmp[i];
            }
        }
    };
    
    // 提取 x 到 w 路径上的值（深度 >= dep[w]）
    for (int i = 0; i <= BIT; i++) {
        if (b[x][i] && d[x][i] >= dep[w]) insert(b[x][i]);
    }
    // 提取 y 到 w 路径上的值
    for (int i = 0; i <= BIT; i++) {
        if (b[y][i] && d[y][i] >= dep[w]) insert(b[y][i]);
    }
    
    // 求最大异或值
    long long ans = 0;
    for (int i = BIT; i >= 0; i--) {
        if ((ans ^ tmp[i]) > ans) ans ^= tmp[i];
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    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);
    
    while (q--) {
        int x, y;
        cin >> x >> y;
        cout << query(x, y) << '\n';
    }
    
    return 0;
}