首先都知道这题得用线性基。
然后预处理出线性基的倍增数组，查询的时候找lca的同时维护路径的线性基数组。
倍增lca复杂度
\(O(logn)\)，合并线性基
\(O(log ^ 2 n)\)，所以总复杂度
\(O(n log ^ 3 n)\)。
注意的是，查询的时候如果一步都跳不了，
\(x\)和
\(y\)所在点的权值就没有加入线性基。所以在跳之前就先把
\(x\)和
\(y\)加入。重了也没有关系。
#include #include #include #include #include #include #include #include #include #include using namespace std;#define enter puts("") #define space putchar(' ')#define Mem(a, x) memset(a, x, sizeof(a))#define In inlinetypedef long long ll;typedef double db;const int INF = 0x3f3f3f3f;const db eps = 1e-8;const int maxn = 2e4 + 5;const int maxb = 15;const int maxN = 60;inline ll read(){ ll ans = 0; char ch = getchar(), last = ' '; while(!isdigit(ch)) {last = ch; ch = getchar();} while(isdigit(ch)) {ans = (ans << 1) + (ans << 3) + ch - '0'; ch = getchar();} if(last == '-') ans = -ans; return ans;}inline void write(ll x){ if(x < 0) x = -x, putchar('-'); if(x >= 10) write(x / 10); putchar(x % 10 + '0');}int n, q;ll a[maxn];struct Edge{ int nxt, to;}e[maxn << 1];int head[maxn], ecnt = -1;In void addEdge(int x, int y){ e[++ecnt] = (Edge){head[x], y}; head[x] = ecnt;}int dep[maxn], fa[maxb + 5][maxn];ll p[maxb + 5][maxn][maxN + 5];In void insert(ll* p, ll x){ for(int i = maxN; i >= 0; --i) { if((x >> i) & 1) { if(p[i]) x ^= p[i]; else {p[i] = x; return;} } }}In void merge(ll* A, ll* B, ll* C){ for(int i = 0; i <= maxN; ++i) C[i] = A[i]; for(int i = 0; i <= maxN; ++i) if(B[i]) insert(C, B[i]);}In void dfs(int now, int _f){ insert(p[0][now], a[now]); for(int i = 1; (1 << i) <= dep[now]; ++i) { fa[i][now] = fa[i - 1][fa[i - 1][now]]; merge(p[i - 1][now], p[i - 1][fa[i - 1][now]], p[i][now]); } for(int i = head[now], v; i != -1; i = e[i].nxt) { if((v = e[i].to) == _f) continue; dep[v] = dep[now] + 1; fa[0][v] = now; insert(p[0][v], a[now]); dfs(v, now); }}ll ans[maxN + 5];In void merge2(ll* ret, ll* a){ for(int i = 0; i <= maxN; ++i) if(a[i]) insert(ret, a[i]);}In ll query(int x, int y){ Mem(ans, 0); insert(ans, a[x]); insert(ans, a[y]); if(dep[x] < dep[y]) swap(x, y); for(int i = maxb; i >= 0; --i) if(dep[x] - (1 << i) >= dep[y]) { merge2(ans, p[i][x]); x = fa[i][x]; } if(x ^ y) { for(int i = maxb; i >= 0; --i) if(fa[i][x] ^ fa[i][y]) { merge2(ans, p[i][x]); merge2(ans, p[i][y]); x = fa[i][x]; y = fa[i][y]; } insert(ans, a[fa[0][x]]); } ll ret = 0; for(int i = maxN; i >= 0; --i) if(!((ret >> i) & 1)) ret ^= ans[i]; return ret;}int main(){ Mem(head, -1); n = read(); q = read(); for(int i = 1; i <= n; ++i) a[i] = read(); for(int i = 1; i < n; ++i) { int x = read(), y = read(); addEdge(x, y); addEdge(y, x); } dfs(1, 0); for(int i = 1; i <= q; ++i) { int x = read(), y = read(); write(query(x, y)), enter; } return 0;}