BZOJ4568: [Scoi2016]幸运数字(线性基 倍增)

题意

题目链接

sol

线性基是可以合并的

倍增维护一下

然后就做完了？？

喵喵喵？

// 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("%lld\n", 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
*/