给定一棵树，每个点有点权。每次询问两个点 \(x,y\)，求 \(x\) 到 \(y\) 的路径上选择若干个点的点权异或和最大值。\(n\leq 2\cdot 10^4,q\leq 2\cdot 10^5\)。
Solution这种树上路径的题一般就是树剖啊点分治啊倍增啊。
这题显然要维护线性基，线性基合并最低复杂度 \(\log^2n\) 。
如果树剖或者倍增维护线性基都是 \(q\log^3 n\) 的，但是都可以在线。
但是如果换成点分治做就是 \(q\log^2 n\) 十分优秀。
每次求出重心到每个点的线性基，只统计过重心的路径的答案即可。
如果一条路径只经过了一个点特判掉即可。
Code #include<bits/stdc++.h> using std::min; using std::max; using std::swap; using std::vector; typedef double db; typedef long long ll; #define pb(A) push_back(A) #define pii std::pair<int,int> #define all(A) A.begin(),A.end() #define mp(A,B) std::make_pair(A,B) #define int long long const int B=62; const int N=20005; vector< pii > v[N]; int head[N],mx[N],vis[N],ok[N],val[N]; int n,m,cnt,tot,root,id,MX,sze[N],ans[N*10]; struct Edge{ int to,nxt; }edge[N<<1]; void add(int x,int y){ edge[++cnt].to=y; edge[cnt].nxt=head[x]; head[x]=cnt; } struct xxj{ int a[B]; xxj(){memset(a,0,sizeof a);} void clear(){memset(a,0,sizeof a);} void ins(int x){ for(int i=61;~i;i--){ if(x>>i&1){ if(!a[i]){ a[i]=x; return; } else x^=a[i]; } } } }f[N]; xxj hb(xxj a,xxj b){ xxj c=a; for(int i=61;~i;i--) if(b.a[i]) c.ins(b.a[i]); return c; } void getroot(int now,int fa=0){ mx[now]=0;sze[now]=1; for(int i=head[now];i;i=edge[i].nxt){ int to=edge[i].to; if(vis[to] or to==fa) continue; getroot(to,now);sze[now]+=sze[to]; mx[now]=max(mx[now],sze[to]); } mx[now]=max(mx[now],tot-sze[now]); if(mx[now]<MX) MX=mx[now],root=now; } int getint(){ int X=0,w=0;char ch=getchar(); while(!isdigit(ch))w|=ch=='-',ch=getchar(); while( isdigit(ch))X=X*10+ch-48,ch=getchar(); if(w) return -X;return X; } int query(xxj a,int now=0){ for(int i=61;~i;i--) if((now^a.a[i])>now) now^=a.a[i]; return now; } void dfs(int now,int fa){ f[now]=f[fa];f[now].ins(val[now]); for(auto x:v[now]){ if(ok[x.first]==id){ xxj c=hb(f[now],f[x.first]);viss[x.second]=1; ans[x.second]=max(ans[x.second],query(c)); } } for(int i=head[now];i;i=edge[i].nxt){ int to=edge[i].to; if(!vis[to] and to!=fa) dfs(to,now); } } void upd(int now,int fa){ ok[now]=id; for(int i=head[now];i;i=edge[i].nxt){ int to=edge[i].to; if(!vis[to] and to!=fa) upd(to,now); } } void solve(int now){ vis[now]=1;id=now;ok[now]=id; f[now].clear();f[now].ins(val[now]); for(int i=head[now];i;i=edge[i].nxt){ int to=edge[i].to; if(!vis[to]) dfs(to,now),upd(to,now); } for(int i=head[now];i;i=edge[i].nxt){ int to=edge[i].to; if(!vis[to]){ tot=sze[to];MX=1e9; getroot(to,0);solve(root); } } } signed main(){ n=getint(),m=getint(); for(int i=1;i<=n;i++) val[i]=getint(); for(int i=1;i<n;i++){ int x=getint(),y=getint(); add(x,y),add(y,x); } for(int i=1;i<=m;i++){ int x=getint(),y=getint(); if(x==y) ans[i]=val[x]; else v[x].pb(mp(y,i)),v[y].pb(mp(x,i)); } tot=n,MX=1e9;getroot(1,0); solve(root); for(int i=1;i<=m;i++) printf("%lld\n",ans[i]); return 0; }