BZOJ4568【SCOI2016】幸运数字 < LCA+线性基 >

Posted on Symbols count in article: 1.2k Reading time ≈ 4 mins.

Problem

【SCOI2016】幸运数字

Time  Limit:  10  Sec\mathrm{Time\;Limit:\;10\;Sec}
Memory  Limit:  256MB\mathrm{Memory\;Limit:\;256MB}

Description

AA国共有nn座城市，这些城市由n−1n-1条道路相连，使得任意两座城市可以互达，且路径唯一。每座城市都有一个幸运数字，以纪念碑的形式矗立在这座城市的正中心，作为城市的象征。一些旅行者希望游览AA国。旅行者计划乘飞机降落在xx号城市，沿着xx号城市到yy号城市之间那条唯一的路径游览，最终从yy城市起飞离开AA国。在经过每一座城市时，游览者就会有机会与这座城市的幸运数字拍照，从而将这份幸运保存到自己身上。然而，幸运是不能简单叠加的，这一点游览者也十分清楚。他们迷信着幸运数字是以异或的方式保留在自己身上的。例如，游览者拍了33张照片，幸运值分别是5,7,115,7,11，那么最终保留在自己身上的幸运值就是 9  (5⊕7⊕11)\mathrm{9\;(5\oplus7\oplus11)}。有些聪明的游览者发现，只要选择性地进行拍照，便能获得更大的幸运值。例如在上述三个幸运值中，只选择55和1111，可以保留的幸运值为1414 。现在，一些游览者找到了聪明的你，希望你帮他们计算出在他们的行程安排中可以保留的最大幸运值是多少。

Input

第一行包含22个正整数n,qn,q，分别表示城市的数量和旅行者数量。第二行包含nn个非负整数，其中第ii个整数GiG_i表示ii号城市的幸运值。随后n−1n-1行，每行包含两个正整数x,yx,y，表示xx号城市和yy号城市之间有一条道路相连。随后qq行，每行包含两个正整数x,yx,y，表示这名旅行者的旅行计划是从xx号城市到yy号城市。

Output

输出需要包含qq行，每行包含11个非负整数，表示这名旅行者可以保留的最大幸运值。

Sample Input

1
2
3
4
5
6
7
4 2
11 5 7 9
1 2
1 3
1 4
2 3
1 4

Sample Output

1
2
14
11

Hint

N≤2×104,  Q≤2×105,  Gi≤260N\le2\times10^4,\;Q\le2\times10^5,\;G_i\le2^{60}

标签：线性基

Solution

最大子集异或和上树…

树上两点间路径，容易联想到倍增LCA\mathrm{LCA}；最大子集异或和，容易联想到线性基。
因此把两者结合起来，预处理出每个结点到其2i2^i祖先结点路径上的线性基，对于倍增的合并，可以暴力合并线性基，即将一个线性基中的数暴力插到另一个线性基中。
求LCA\mathrm{LCA}的过程照常，只是将单个值合并换成了两个数组合并。

Code

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
#include <bits/stdc++.h>
#define SZ 60
#define LOG 15
#define MAX_N 20000
#define vl vector<lnt>
using namespace std;
typedef long long lnt;
template <class T>
inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
lnt a[MAX_N+5];
int n, q, fa[MAX_N+5][LOG+1], dep[MAX_N+5];
vector <lnt> b[MAX_N+5][LOG+1]; vector <int> G[MAX_N+5];
void addedge(int u, int v) {G[u].push_back(v), G[v].push_back(u);}
lnt get_mx(vl base) {
    lnt ret = 0LL;
    for (int i = SZ; ~i; i--) if (base[i])
        if ((ret^base[i]) > ret) ret ^= base[i];
    return ret;
}
vl merge(vl x, vl y) {
    vl ret = x;
    for (int i = SZ; ~i; i--) if (y[i])
        for (int j = i; ~j; j--) if (y[i]>>j&1) {
            if (ret[j]) y[i] ^= ret[j];
            else {ret[j] = y[i]; break;}
        }
    return ret;
}
void DFS(int u) {
    b[u][0].resize(SZ+1);
    for (int i = SZ; ~i; i--)
        if (a[u]>>i&1) {b[u][0][i] = a[u]; break;}
    for (int i = 1; i <= LOG; i++)
        fa[u][i] = fa[fa[u][i-1]][i-1], b[u][i].resize(SZ+1), 
            b[u][i] = merge(b[u][i-1], b[fa[u][i-1]][i-1]);
    for (int i = 0, v; i < (int)G[u].size(); i++)
        if ((v = G[u][i]) ^ fa[u][0])
            fa[v][0] = u, dep[v] = dep[u]+1, DFS(v);
}
lnt query(int u, int v) {
    vl ub, vb;	ub.resize(SZ+1), vb.resize(SZ+1);
    if (dep[u] < dep[v]) swap(u, v);
    for (int i = LOG; ~i; i--) if (dep[u]-dep[v] >= (1<<i))
        ub = merge(ub, b[u][i]), u = fa[u][i];
    if (u == v) return get_mx(merge(ub, b[u][0]));
    for (int i = LOG; ~i; i--) if (fa[u][i]^fa[v][i])
        ub = merge(ub, b[u][i]), u = fa[u][i],
        vb = merge(vb, b[v][i]), v = fa[v][i];
    ub = merge(ub, b[u][0]), vb = merge(vb, b[v][0]);
    return get_mx(merge(merge(ub, vb), b[fa[u][0]][0]));
}
int main() {
    read(n), read(q);
    for (int i = 1; i <= n; i++) read(a[i]);
    for (int i = 1, u, v; i < n; i++)
        read(u), read(v), addedge(u, v);
    for (int i = 0; i <= LOG; i++) b[0][i].resize(SZ+1);
    DFS(1);
    while (q--) {
        int u, v;	read(u), read(v);
        printf("%lld\n", query(u, v));
    }
    return 0;
}