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

*/

巴特西

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

题意

Sol

最新文章

热门文章

巴特西

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

题意

Sol

最新文章

热门文章

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