简要题意

给你一颗点有点权的树, 次询问, 每次询问两点间路径点权的子集的最大异或和

#2013. 「SCOI2016」幸运数字

题目描述

A 国共有 座城市，这些城市由 条道路相连，使得任意两座城市可以互达，且路径唯一。每座城市都有一个幸运数字，以纪念碑的形式矗立在这座城市的正中心，作为城市的象征。

一些旅行者希望游览 A 国。旅行者计划乘飞机降落在 号城市，沿着 号城市到 号城市之间那条唯一的路径游览，最终从 城市起飞离开 A 国。在经过每一座城市时，游览者就会有机会与这座城市的幸运数字拍照，从而将这份幸运保存到自己身上。然而，幸运是不能简单叠加的，这一点游览者也十分清楚。他们迷信着幸运数字是以异或的方式保留在自己身上的。

例如，游览者拍了 张照片，幸运值分别是 ，，，那么最终保留在自己身上的幸运值就是 （ xor xor ）。

有些聪明的游览者发现，只要选择性地进行拍照，便能获得更大的幸运值。例如在上述三个幸运值中，只选择 和 ，可以保留的幸运值为 。现在，一些游览者找到了聪明的你，希望你帮他们计算出在他们的行程安排中可以保留的最大幸运值是多少。

输入格式

第一行包含 个正整数 ，，分别表示城市的数量和旅行者数量。

第二行包含 个非负整数，其中第 个整数 表示 号城市的幸运值。

随后 行，每行包含两个正整数 ，，表示 号城市和 号城市之间有一条道路相连。

随后 行，每行包含两个正整数 ，，表示这名旅行者的旅行计划是从 号城市到 号城市。

输出格式

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

输入输出样例

略.....

题解

最大异或和......显然是线性基

考虑怎么把线性基放到树上, 一个比较朴素的想法是每次询问 , 把路径上的点的点权放进线性基里来求最大异或和.

这样显然是过不了的, 我们考虑如何优化. 其实查询 路径上的最大异或和是相当于合并 到其 LCA 与 到其 LCA 的线性基, 于是直接倍增维护就好了.......

然后就直接过掉了..

代码:

#include <bits/stdc++.h>

#ifndef __HEADERS__
#define __HEADERS__

#define up(i,j,k) for (int i = j; i <= k; i++)
#define down(i,j,k) for (int i = j; i >= k; i--)

#define ll long long
#define ull unsigned long long

#define mp std::make_pair
#define pb push_back
#define x first
#define y second

#define all(x) x.begin(), x.end()
#define lowbit(x) ((x) & (-x))
#define mem(a) memset(a, 0, sizeof(a))
#define File(x)                       \
    freopen("" #x ".in", "r", stdin); \
    freopen("" #x ".out", "w", stdout);

#endif

#define ul unsigned long long
#define int long long

inline int read() {
    int data = 0, w = 1; char ch = 0;
    while (ch != '-' && (ch > '9' || ch < '0')) ch = getchar(); if (ch == '-') w = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') { data = data * 10 + ch - '0'; ch = getchar(); }
    return data * w;
}

inline void print (ul v) {
    if (v > 9) print(v / 10);
    putchar(v % 10 + '0');
}

const int N = 100000 + 10;
const int M = 200000 + 10;
const int logN = 62;

int n, m;
std::vector <int> e[N];

void insert (ul *a, ul x) {
    down (i, 61, 0)
        if (x & (1ll << i)) {
            if (a[i]) x ^= a[i];
            else {
                a[i] = x;
                break;
            }
        }
}

ul query (ul *a) {
    ul x = 0;
    down (i, logN, 0)
        if (x < (x ^ a[i])) x ^= a[i];
    return x;
}

void merge (ul *a, ul *b) {
    down (i, logN, 0) {
        if (b[i]) insert(a, b[i]);
    }
}

void cl (ul *a) {
    memset (a, 0, sizeof (ul) * logN);
}

void cpy (ul *a, ul *b) {
    memcpy(a, b, sizeof (ul) * logN);
}

inline void add (int u, int v) { e[u].pb(v); e[v].pb(u); }

int dep[N];
int f[N][21];
ul p[N][21][70];

void dfs (int u, int fa) {
    f[u][0] = fa;
    dep[u] = dep[fa] + 1;
    for (auto i : e[u]) {
        if (i == fa) continue;
        dfs(i, u);
    }
}

void pre() {
    up (j, 1, 19)
        up (i, 1, n) {
            f[i][j] = f[f[i][j - 1]][j - 1];
//            cpy(p[i][j], p[i][j - 1]);
            memcpy(p[i][j], p[i][j - 1], sizeof(p[i][j - 1]));
            merge(p[i][j], p[f[i][j - 1]][j - 1]);
        }
}

ul ans[logN];
inline void lca(int u, int v) {
    if (dep[u] < dep[v]) std::swap(u, v);
    down (i, 20, 0)
        if(dep[f[u][i]] >= dep[v])
            merge(ans, p[u][i]), u = f[u][i];
    if(u == v) {
        merge(ans, p[u][0]);
        return;
    }
    down (i, 20, 0)
        if(f[u][i] != f[v][i]) {
            merge(ans, p[u][i]), merge(ans, p[v][i]);
            u = f[u][i], v = f[v][i];
        }
    merge(ans, p[u][0]), merge(ans, p[v][0]);
    merge(ans, p[f[u][0]][0]);
}

signed main () {
    n = read();
    int q = read();
    up (i, 1, n) insert(p[i][0], read());
    up (i, 1, n - 1) {
        add(read(), read());
    }
    dfs(1, 0);
    pre();
    int u, v;
    while (q --> 0) {
        cl(ans);
        u = read(); v = read();
        lca(u, v);
        print(query(ans)); putchar('\n'); 
    }
    return 0;
}