[BZOJ4568]幸運數
摘要：
線性基+倍增暴力維護
好難啊難啊啊
給定一顆n個節點的樹，每個點有一個權值\(a_i\)
，大小在\(2^{60}\)
內，有q組詢問，每次給定u，v，詢問u到v的路徑上的點的最大子集異或和。
最開始想的是莫隊能不能搞一下，但是線性基...
線性基+倍增暴力維護
好難啊難啊啊
- 給定一顆n個節點的樹，每個點有一個權值\(a_i\) ，大小在\(2^{60}\) 內，有q組詢問，每次給定u，v，詢問u到v的路徑上的點的最大子集異或和。
- 最開始想的是莫隊能不能搞一下，但是線性基怎麼刪除了，所以不可行。
- 那還能什麼辦法啊QAQ。處理樹上路徑問題，好用的就只剩倍增了吧。
- 這時候你可能會有質疑了，倍增怎麼優秀維護線性基啊？不急，不需要優秀，暴力往上懟，把你想到的暴力打上去。暴力求會吧？會吧？會吧？就是你每一個f【x】【i】維護一個線性基，倍增向上跳的時候直接暴力合併。那麼思路就很清晰了，程式碼也很好寫（至少沒太多細節，不用犯sb錯誤）。
Coding
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e4+10;
const int MAXN=63;
int n,q,tot,ver[N<<1],Next[N<<1],lin[N],dep[N],fa[N][25];ll val[N],f[N][25][64],c[100];
void insert(ll *a,ll v){
for(int i=MAXN;i>=0;--i) if((v>>i)&1){
if(a[i]) v^=a[i];
else{
for(int j=i-1;j>=0;--j)
if((v>>j)&1) v^=a[j];
for(int j=i+1;j<=MAXN;++j)
if((a[j]>>i)&1) a[j]^=v;
a[i]=v;
break;
}
}
}
void add(int x,int y){
ver[++tot]=y;Next[tot]=lin[x];lin[x]=tot;
}
void merge(ll *a,ll *b){
for(int i=0;i<=MAXN;++i) if(b[i]) insert(a,b[i]);
}
void dfs(int x,int ff){
fa[x][0]=ff;dep[x]=dep[ff]+1;
insert(f[x][0],val[ff]);
for(int i=1;i<=20;++i){
if((1<<i)<=dep[x]){
fa[x][i]=fa[fa[x][i-1]][i-1];
memcpy(f[x][i],f[x][i-1],sizeof(f[x][i]));
merge(f[x][i],f[fa[x][i-1]][i-1]);
}
}
for(int i=lin[x];i;i=Next[i]){
int y=ver[i];
if(y==ff) continue;
dfs(y,x);
}
}
void lca(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
insert(c,val[x]);insert(c,val[y]);
for(int i=20;i>=0;--i){
if(dep[fa[x][i]]>=dep[y]){
merge(c,f[x][i]);x=fa[x][i];
}
}
if(x==y) return;
for(int i=20;i>=0;--i){
if(fa[x][i]!=fa[y][i]){
merge(c,f[x][i]);
merge(c,f[y][i]);
x=fa[x][i],y=fa[y][i];
}
}
insert(c,val[fa[x][0]]);
}
int main(){
scanf("%d%d",&n,&q);
for(int i=1;i<=n;++i) scanf("%lld",&val[i]);
for(int i=1;i<n;++i){
int x,y;scanf("%d%d",&x,&y);
add(x,y);add(y,x);
}dep[0]=-1;
dfs(1,0);
for(int i=1;i<=q;++i){
memset(c,0,sizeof(c));
int x,y;scanf("%d%d",&x,&y);
lca(x,y);
ll ans=0;
for(int i=MAXN;i>=0;--i) ans=max(ans,ans^c[i]);
printf("%lld\n",ans);
}
return 0;
}