题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4757
题意:给出一棵树,节点有权值。每次询问x到y的路径上与z抑或的最大值。
思路:可持久化trie。
struct Node { int c[2],cnt; }; Node a[2000005]; int cnt; int newNode() { cnt++; a[cnt].c[0]=a[cnt].c[1]=a[cnt].cnt=0; return cnt; } struct node { int v,next; }; node edges[N<<1]; int head[N],e; void add(int u,int v) { edges[e].v=v; edges[e].next=head[u]; head[u]=e++; } int n,m,f[N][20],d[N],dep[N],root[N]; void insert(int u,int p,int d) { int x=root[u],y=root[p],i,k; for(i=15;i>=0;i--) { k=(d>>i)&1; a[x].c[k]=newNode(); a[x].c[!k]=a[y].c[!k]; a[a[x].c[k]].cnt=a[a[y].c[k]].cnt+1; x=a[x].c[k]; y=a[y].c[k]; } } void DFS(int u,int pre) { f[u][0]=pre; dep[u]=dep[pre]+1; root[u]=newNode(); insert(u,pre,d[u]); int i,v; for(i=head[u];i!=-1;i=edges[i].next) { v=edges[i].v; if(v==pre) continue; DFS(v,u); } } int getLca(int x,int y) { if(dep[x]>dep[y]) swap(x,y); int i,k=dep[y]-dep[x]; FOR0(i,16) if(k&(1<<i)) y=f[y][i]; if(x==y) return x; for(i=16;i>=0;i--) { if(f[x][i]&&f[y][i]&&f[x][i]!=f[y][i]) { x=f[x][i]; y=f[y][i]; } } return f[x][0]; } int cal(int x,int y,int z,int val) { int i,k,ans=0,t=f[z][0]; x=root[x]; y=root[y]; z=root[z]; t=root[t]; for(i=15;i>=0;i--) { k=!((val>>i)&1); int xx=a[x].c[k]; int yy=a[y].c[k]; int zz=a[z].c[k]; int tt=a[t].c[k]; if(a[xx].cnt+a[yy].cnt-a[zz].cnt-a[tt].cnt>0) ans|=1<<i; else k=!k; x=a[x].c[k]; y=a[y].c[k]; z=a[z].c[k]; t=a[t].c[k]; } return ans; } int main() { while(scanf("%d%d",&n,&m)!=-1) { int i; FOR1(i,n) RD(d[i]),head[i]=-1; cnt=0; e=0; FOR1(i,n-1) { int u,v; RD(u,v); add(u,v); add(v,u); } clr(f,0); DFS(1,0); int j; for(i=1;i<=16;i++) FOR1(j,n) { f[j][i]=f[f[j][i-1]][i-1]; } while(m--) { int x,y,z; RD(x,y,z); PR(cal(x,y,getLca(x,y),z)); } } }