考点:可持久化01树,LCA,贪心
对整个图建可持久化01树,其父版本是图上的父亲
对于每次询问,LCA得出其最近公共祖先
利用01树找到表演风格相差最大的城市
利用差分求出其他城市的异或和
最后通过贪心计算答案
#include<bits/stdc++.h> using namespace std; const int N=2e5+5; int tot; int cnt; int x[N]; int n,m,w; int head[N]; int tr[N<<6][2]; int f[N][20],dep[N]; int siz[N<<6],Xor[N],rt[N]; struct Edge{ int u,v; }edge[N<<1]; void add(int x,int y){ edge[++tot].u=head[x]; edge[tot].v=y; head[x]=tot; return ; } void insert(int now,int pre,int val){ for(int i=1<<30; i; i>>=1){ bool k=val&i; tr[now][k^1]=tr[pre][k^1]; tr[now][k]=cnt++; siz[tr[now][k]]=siz[tr[pre][k]]+1; now=tr[now][k]; pre=tr[pre][k]; } } void dfs(int now,int fa){ f[now][0]=fa; dep[now]=dep[fa]+1; Xor[now]=Xor[fa]^x[now]; for(int i=1; i<20; ++i) f[now][i]=f[f[now][i-1]][i-1]; for(int i=head[now]; i; i=edge[i].u){ int to=edge[i].v; if(to==fa) continue; rt[to]=cnt++; insert(rt[to],rt[now],x[to]); dfs(to,now); } } int query(int now,int pre,int val){ int res=0; for(int i=1<<30; i; i>>=1){ bool k=val&i; if(siz[tr[pre][k^1]]>siz[tr[now][k^1]]){ res+=i; now=tr[now][k^1]; pre=tr[pre][k^1]; }else{ now=tr[now][k]; pre=tr[pre][k]; } } return res; } int LCA(int x,int y){ if(dep[x]<dep[y]) swap(x,y); for(int i=19; i>=0; --i){ if(dep[f[x][i]]>=dep[y]) x=f[x][i]; if(x==y) return x; } for(int i=19; i>=0; --i) if(f[x][i]!=f[y][i]){ x=f[x][i]; y=f[y][i]; } return f[x][0]; } int solve(int u,int v,int p){ int lca=LCA(u,v); int maxx=0,ans=0; int res=Xor[u]^Xor[v]; maxx=max(maxx,query(rt[lca],rt[u],p)); maxx=max(maxx,query(rt[lca],rt[*** maxx=max(maxx,x[lca]^p); res=res^x[lca]^maxx^p; for(int i=30; i>=0; --i){ if((ans|(1<<i))>w) continue; if(res&(1<<i)) continue; ans|=(1<<i); } return ans|res; } int main(){ scanf("%d%d%d",&n,&m,&w); for(int i=1,p,q; i<n; ++i){ scanf("%d%d",&p,&q); add(p,q); add(q,p); } for(int i=1; i<=n; ++i) scanf("%d",&x[i]); cnt=1; rt[1]=cnt++; insert(rt[1],0,x[1]); dfs(1,0); for(int i=1,u,v,s; i<=m; ++i){ scanf("%d%d%d",&u,&v,&s); printf("%d\n",solve(u,v,s)); } return 0; }