先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; }