「BZOJ-4568」[Scoi2016]幸运数字(倍增+线性基)

发表于 | 分类于 ，

BZOJ4568-[Scoi2016]幸运数字
在树上路径(u,v)之间选择一些点的权值，使异或和最大

题解

对于树上的每一个点，维护log(n)个线性基，L[u][i]表示从它自身到它上跳$2^i$倍祖先的线性基，在对LCA做预处理的时候预处理出单个节点的倍增线性基。查询LCA时每次上跳都对答案插入当前节点上跳$2^i$倍的线性基，最后要单独插入点$a[v]$的值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 2e4 + 10;

vector<int> edge[maxn];

int n, dep[maxn], fa[maxn][20]; ll a[maxn];

struct LinearBasis
{
    ll d[64], tot;

    LinearBasis()
    {
        memset(d, 0, sizeof d);
        tot = 0;
    }

    void ins(ll x)
    {
        for(int i = 63; i >= 0; i --) if((x >> i) & 1)
        {
            if(d[i]) x ^= d[i];
            else { d[i] = x; tot ++; return; }
        }
    }

    ll max_xor()
    {
        ll ans = 0;
        for(int i = 63; i >= 0; i --) if((ans ^ d[i]) > ans) ans ^= d[i];
        return ans;
    }

    void Merge(LinearBasis &a) { for(int i = 63; i >= 0; i --) if(a.d[i]) ins(a.d[i]); }
}L[maxn][20];

LinearBasis merge(const LinearBasis &a, const LinearBasis &b)
{
	LinearBasis res = a;
	for(int i = 63; i >= 0; i --) if(b.d[i]) res.ins(b.d[i]);
	return res;
}

void dfs(int u, int pre)
{
    dep[u] = dep[pre] + 1, fa[u][0] = pre;
    L[u][0].ins(a[pre]); L[u][0].ins(a[u]);
    for(int i = 1; (1 << i) <= n; i ++)
    {
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
        L[u][i].Merge(L[u][i - 1]);
        L[u][i].Merge(L[fa[u][i - 1]][i - 1]);
    }
    for(int i = 0; i < edge[u].size(); i ++) {int v = edge[u][i]; if(v != pre) dfs(v, u); }
}

LinearBasis LCA(int u, int v)
{
    LinearBasis res;
    if(dep[u] < dep[v]) swap(u, v);
    int d = dep[u] - dep[v];
    for(int i = 0; (1 << i) <= d; i ++) if((1 << i) & d) res.Merge(L[u][i]), u = fa[u][i];
    if(u == v) { res.ins(a[v]); return res; }
    for(int i = 19; i >= 0; i --) if(fa[u][i] != fa[v][i]) res.Merge(L[u][i]), res.Merge(L[v][i]), u = fa[u][i], v = fa[v][i];
    res.Merge(L[u][0]), res.ins(a[v]);
    return res;
}

int main()
{
    int q, u, v;
    scanf("%d%d", &n, &q);
    for(int i = 1; i <= n; i ++) scanf("%lld", &a[i]);
    for(int i = 1; i < n; i ++)
    {
        scanf("%d%d", &u, &v);
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    dfs(1, 0);
    while(q --)
    {
        scanf("%d%d", &u, &v);
        LinearBasis ans = LCA(u, v);
        printf("%lld\n", ans.max_xor());
    }
    return 0;
}