题解 | #武侍乐队#

先dfs预处理出异或和，再用可持久化Trie，pre版本是u，v的的最近公共祖先，now版本是u（v），cnt数组存某个下标的01数量，查询时只cnt[pre]<cnt[now]即可往这个分支走，最后再贪心

#include<bits/stdc++.h>

#define pb push_back
using namespace std;
const int N = 2e5 + 10;
vector<int> v[N];
int x[N], f[N][20], dep[N], xo[N], cnt[32 * N], rt[N], idx, tr[32 * N][2];

void insert(int pre, int now, int val) {
    for (int i = 30; i >= 0; i--) {
        bool v = val >> i & 1;
        tr[now][v ^ 1] = tr[pre][v ^ 1];
        tr[now][v] = ++idx;
        now = tr[now][v];
        pre = tr[pre][v];
        cnt[now] = cnt[pre] + 1;
    }
}

void dfs(int u, int fa) {
    f[u][0] = fa;
    dep[u] = dep[fa] + 1;
    xo[u] = xo[fa] ^ x[u];
    for (int i = 1; i < 20; i++)f[u][i] = f[f[u][i - 1]][i - 1];
    insert(rt[fa], rt[u]=++idx, x[u]);
    for (auto i:v[u])
        if (i != fa)
            dfs(i, u);
}

int lca(int x, int y) {
    if (dep[x] < dep[y])swap(x, y);
    for (int i = 19; i >= 0; i--)
        if (dep[f[x][i]] >= dep[y])
            x = f[x][i];

    if (x == y)return x;

    for (int i = 19; i >= 0; i--)
        if (f[x][i] != f[y][i])
            x = f[x][i], y = f[y][i];
    return f[x][0];
}

int query(int now, int pre, int val) {
    int res = 0;
    for (int i = 30; i >= 0; i--) {
        bool v = val >> i & 1;
        if (cnt[tr[now][v ^ 1]] > cnt[tr[pre][v ^ 1]]) {
            res += 1 << i;
            v^=1;
        }
        now = tr[now][v];
        pre = tr[pre][v];
    }
    return res;
}

int main() {
    int n, m, w;
    scanf("%d%d%d", &n, &m, &w);
    for (int i = 1; i < n; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        v[x].pb(y);
        v[y].pb(x);
    }
    for (int i = 1; i <= n; i++)scanf("%d", &x[i]);
    dfs(1, 0);
    while (m--) {
        int a, b, s;
        scanf("%d%d%d", &a, &b, &s);
        int p = lca(a, b);
        int ans = xo[a] ^xo[b] ^x[p];
        int ma = max({query(rt[b], rt[p], s), query(rt[a], rt[p], s), x[p] ^ s});
        ans = ans ^ ma ^ s;
        int res = 0;
        for (int k = 30; ~k; --k)if (!(ans & (1 << k)) && res + (1 << k) <= w)res += (1 << k);
        cout << (ans ^ res) << endl;
    }
    return 0;
}