题目：P3292 [SCOI2016]幸运数字

题目大意：

给一颗树 (n\le 10^4)，每个点有一个权值。有 q 组询问 (q\le 10^5)，问两点之间树上路径点的最大异或和。

解题思路：

首先树剖，给点重新赋 id；用树剖算 lca 的过程中，对每条链维护一个线性基，每次将链的线性基和答案的线性基合并。由于经过了树剖重新赋值，我们可以对整棵树维护一个前缀线性基，每次将一部分与答案线性基合并即可。

这里注意，合并线性基就是把一个线性基中的全部元素插入到另一个线性基中。

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 50;
const int M = 62;
long long a[N];

int n, q;
int head[N], tot;
struct Edge {
    int nex, to;
}e[N << 1];
void add(int a, int b) {
    e[++tot] = (Edge){head[a], b};
    head[a] = tot;
}

int id[N], cnt;
long long w[N];
struct Node {
    int dep, fa, sz;
    int mson, top;
}nd[N];
void dfs1(int rt, int fa, int dep) {
    nd[rt].dep = dep; nd[rt].fa = fa; nd[rt].sz = 1;
    int mson = -1;
    for (int i = head[rt]; i; i = e[i].nex) {
        int to = e[i].to;
        if (to == fa) continue;
        dfs1(to, rt, dep + 1);
        nd[rt].sz += nd[to].sz;
        if (nd[to].sz > mson) {
            mson = nd[to].sz;
            nd[rt].mson = to;
        }
    }
}
void dfs2(int rt, int tp) {
    id[rt] = ++cnt; w[cnt] = a[rt];
    nd[rt].top = tp;
    if (!nd[rt].mson) return;
    dfs2(nd[rt].mson, tp);
    for (int i = head[rt]; i; i = e[i].nex) {
        int to = e[i].to;
        if (to == nd[rt].fa || to == nd[rt].mson) continue;
        dfs2(to, to);
    }
}

struct Prifix_LB {
    long long d[M + 5]; int pos[M + 5];
    void init() {
        memset(d, 0, sizeof(d));
        memset(pos, 0, sizeof(pos));
    }
    void insert(Prifix_LB &lst, int id, long long w) {
        *this = lst;
        for (int i = M; i >= 0; i--) {
            if ((w >> i) & 1) {
                if (!d[i]) {
                    d[i] = w; pos[i] = id; return;
                }
                else if (pos[i] < id) {
                    swap(id, pos[i]); swap(w, d[i]);
                }
                w ^= d[i];
            }
        }
    }
}LB[N];

struct Linear_Base{
    long long d[100]; int tot;
    void init() {
        tot = 0;
        memset(d, 0, sizeof(d));
    }
    void insert(long long x) {
        for (int i = M; i >= 0; i--) {
            if (!(x >> i)) continue;
            if (!d[i]) {
                d[i] = x; tot++; return;
            }
            x ^= d[i];
        }
    }
    void merge(int l, int r) {
        for (int i = 0; i <= M; i++) {
            if (LB[r].d[i] && LB[r].pos[i] >= l) {
                insert(LB[r].d[i]);
            }
        }
    }
    long long qmax() {
        long long ans = 0;
        for (int i = M; i >= 0; i--) {
            if ((ans ^ d[i]) > ans) ans ^= d[i];
        }
        return ans;
    }
}ans;

#define topx nd[x].top
#define topy nd[y].top
long long solve(int x, int y) {
    while (topx != topy) {
        if (nd[topx].dep < nd[topy].dep) {
            ans.merge(id[topy], id[y]);
            y = nd[topy].fa;
        }
        else {
            ans.merge(id[topx], id[x]);
            x = nd[topx].fa;
        }
    }
    if (nd[x].dep < nd[y].dep) ans.merge(id[x], id[y]);
    else ans.merge(id[y], id[x]);
    return ans.qmax();
}

int main(int argc, const char * argv[]) {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    for (int i = 1, a, b; i < n; i++) {
        scanf("%d%d", &a, &b);
        add(a, b); add(b, a);
    }
    dfs1(1, 0, 1); dfs2(1, 1);
    for (int i = 1; i <= n; i++) {
        LB[i].insert(LB[i - 1], i, w[i]);
    }
    for (int i = 1, x, y; i <= q; i++) {
        scanf("%d%d", &x, &y);
        ans.init();
        printf("%lld\n", solve(x, y));
    }
    return 0;
}