题目大意：给一棵$n(n\leqslant2\times10^4)$个点的树，$m(m\leqslant2\times10^5)$个询问，每次问$x->y$路径上的树异或最大值
题解：可以点分治，线性基合并即可
卡点：一处查询的地方写成了$maxn$
C++ Code：
#include#include #include namespace __IO { namespace R { int x, ch; inline int read() { ch = getchar(); while (isspace(ch)) ch = getchar(); for (x = ch & 15, ch = getchar(); isdigit(ch); ch = getchar()) x = x * 10 + (ch & 15); return x; } long long X; inline long long readll() { ch = getchar(); while (isspace(ch)) ch = getchar(); for (X = ch & 15, ch = getchar(); isdigit(ch); ch = getchar()) X = X * 10 + (ch & 15); return X; } }}using __IO::R::read;using __IO::R::readll;#define maxn 20010#define maxm 200010const int inf = 0x3f3f3f3f;int head[maxn], cnt = 1;struct Edge { int to, nxt;} e[maxn << 1];inline void addedge(int a, int b) { e[++cnt] = (Edge) {b, head[a]}; head[a] = cnt; e[++cnt] = (Edge) {a, head[b]}; head[b] = cnt;}int headq[maxm], cntq = 1;struct Query { int to, nxt; bool vis;} qu[maxm << 1];inline void addquery(int a, int b) { qu[++cntq] = (Query) {b, headq[a], false}; headq[a] = cntq; qu[++cntq] = (Query) {a, headq[b], false}; headq[b] = cntq;}struct Base {#define M 60 long long s[M + 1]; inline Base& init() { for (int i = 0; i <= M; i++) s[i] = 0; return *this; } inline Base& insert(long long x) { for (int i = M; ~i; i--) if (x >> i & 1) { if (s[i]) x ^= s[i]; else {s[i] = x; break;} } return *this; } inline friend Base operator + (Base a, const Base &b) { for (int i = M; ~i; i--) if (b.s[i]) a.insert(b.s[i]); return a; } long long query() { long long ans = 0; for (int i = M; ~i; i--) if (ans < (ans ^ s[i])) ans ^= s[i]; return ans; }#undef M} f[maxn];bool vis[maxn];namespace Center_of_Gravity { int sz[maxn], __nodenum; int root, MIN;#define n __nodenum void __getroot(int u, int fa = 0) { sz[u] = 1; int MAX = 0; for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to; if (v != fa && !vis[v]) { __getroot(v, u); sz[u] += sz[v]; MAX = std::max(MAX, sz[v]); } } MAX = std::max(MAX, n - sz[u]); if (MAX < MIN) MIN = MAX, root = u; } int getroot(int u, int nodenum = 0) { n = nodenum ? nodenum : sz[u]; MIN = inf; __getroot(u); return root; }#undef n}using Center_of_Gravity::getroot;int n, Q;long long w[maxn], ans[maxm];int S[maxn], top, bel[maxn];void getlist(int u, int fa, int tg) { bel[S[top++] = u] = tg; (f[u] = f[fa]).insert(w[u]); for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to; if (v != fa && !vis[v]) getlist(v, u, tg); }}void solve(int u) { vis[u] = true, (f[u].init()).insert(w[u]), top = 0; for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to; if (!vis[v]) getlist(v, u, v); } for (int i = headq[u]; i; i = qu[i].nxt) if (!qu[i].vis){ ans[i >> 1] = f[qu[i].to].query(); qu[i].vis = qu[i ^ 1].vis = true; } for (int j = 0; j < top; j++) { int u = S[j]; for (int i = headq[u]; i; i = qu[i].nxt) if (!qu[i].vis) { int v = qu[i].to; if (bel[u] != bel[v]) { ans[i >> 1] = (f[u] + f[v]).query(); qu[i].vis = qu[i ^ 1].vis = true; } } } for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to; if (!vis[v]) solve(getroot(v)); }}int main() { n = read(), Q = read(); for (int i = 1; i <= n; i++) w[i] = readll(); for (int i = 1, a, b; i < n; i++) { a = read(), b = read(); addedge(a, b); } for (int i = 0, a, b; i < Q; i++) { a = read(), b = read(); addquery(a, b); } solve(getroot(1, n)); for (int i = 1; i <= Q; i++) printf("%lld\n", ans[i]); return 0;}