P3292 [SCOI2016]幸运数字

题意：询问树上两点间的最大异或和 最大异或和可以用线性基解决 先树剖，用线段树维护每一条链的最大异或和就搞定了 注意pushup的不同 ``` #include<cstdio> #include<cstring> #include<cctype> #include<algorithm> #define reg register using namespace std; typedef long long ll; const int N=2e4+5; struct node { int to,nxt; }edge[N<<1]; int n,m,num,head[N],fa[N],son[N],tot[N]; int cnt,idx[N],dep[N],top[N]; ll w[N],a[N],s[N<<2][63],f[65],tmp[65]; inline ll read() { ll x=0,w=1; char c=getchar(); while (!isdigit(c)&&c!='-') c=getchar(); if (c=='-') c=getchar(),w=0; while (isdigit(c)) { x=(x<<1)+(x<<3)+c-'0'; c=getchar(); } return w?x:-x; } inline void add_edge(int from,int to) { edge[++num]=(node){to,head[from]}; head[from]=num; } void dfs(int k,int father,int deep) { int bigson=0; fa[k]=father; dep[k]=deep; tot[k]=1; for (reg int i=head[k];i;i=edge[i].nxt) { int v=edge[i].to; if (v==father) continue; dfs(v,k,deep+1); tot[k]+=tot[v]; if (bigson<tot[v]) { bigson=tot[v]; son[k]=v; } } } void dfs(int k,int tp) { idx[k]=++cnt; top[k]=tp; a[cnt]=w[k]; if (!son[k]) return; dfs(son[k],tp); for (reg int i=head[k];i;i=edge[i].nxt) { int v=edge[i].to; if (!idx[v]) dfs(v,v); } } inline void insert(ll *a,ll x) { for (reg int i=60;~i;i--) if (x&(1ll<<i)) if (!a[i]) {a[i]=x; break;} else x^=a[i]; } inline void merge(ll *a,ll *b) { for (reg int i=60;~i;i--) if (b[i]) insert(a,b[i]); } inline ll query() { ll ans=0; for (reg int i=60;~i;i--) if (ans<(ans^f[i])) ans^=f[i]; return ans; } void build(int l,int r,int now) { if (l==r) { insert(s[now],a[l]); return; } int mid=(l+r)>>1; build(l,mid,now<<1); build(mid+1,r,now<<1|1); merge(s[now],s[now<<1]); merge(s[now],s[now<<1|1]); } void Query(int L,int R,int l,int r,int now) { if (l>R||r<L) return; if (l>=L&&r<=R) {merge(tmp,s[now]); return;} int mid=(l+r)>>1; if (mid>=R) Query(L,R,l,mid,now<<1); else if (mid<L) Query(L,R,mid+1,r,now<<1|1); else { Query(L,mid,l,mid,now<<1); Query(mid+1,R,mid+1,r,now<<1|1); } } inline ll getans(int x,int y) { memset(f,0,sizeof(f)); while (top[x]!=top[y]) { if (dep[top[x]]<dep[top[y]]) swap(x,y); memset(tmp,0,sizeof(tmp)); Query(idx[top[x]],idx[x],1,n,1); merge(f,tmp); x=fa[top[x]]; } if (dep[x]>dep[y]) swap(x,y); memset(tmp,0,sizeof(tmp)); Query(idx[x],idx[y],1,n,1); merge(f,tmp); return query(); } int main() { n=read(),m=read(); for (reg int i=1;i<=n;w[i++]=read()); for (reg int i=1;i<n;i++) { int x=read(),y=read(); add_edge(x,y); add_edge(y,x); } dfs(1,0,1); dfs(1,1); build(1,n,1); while (m--) { int x=read(),y=read(); printf("%lld\n",getans(x,y)); } return 0; } ```