https://www.lydsy.com/JudgeOnline/problem.php?id=5338
现在有一颗以1为根节点的由n个节点组成的树，树上每个节点上都有一个权值vi。现在有Q 次操作，操作如下:1 x y 查询节点x的子树中与y异或结果的最大值2 x y z 查询路径x到y上点与z异或结果最大值
别的不想多说了，出原题不怕被骂吗……
#include<cmath> #include<queue> #include<cstdio> #include<cctype> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int N=1e5+5; inline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X; } struct trie{ int son[2],sum; }tr[80*N]; struct node{ int to,nxt; }e[N*2]; int tot,a[N],rt[N*2],pool,cnt,head[N],idx[N]; int dep[N],anc[N][20],n,q,pos[N],id,size[N]; inline void add(int u,int v){ e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt; } void insert(int y,int &x,int k,int now){ tr[x=++pool]=tr[y]; tr[x].sum++; if(now<0)return; bool p=k&(1<<now); insert(tr[y].son[p],tr[x].son[p],k,now-1); return; } int query(int nl,int nr,int k,int now){ if(now<0)return 0; bool p=k&(1<<now); int delta=tr[tr[nr].son[p^1]].sum-tr[tr[nl].son[p^1]].sum; if(delta>0)return (1<<now)+query(tr[nl].son[p^1],tr[nr].son[p^1],k,now-1); else return query(tr[nl].son[p],tr[nr].son[p],k,now-1); } void dfs(int u,int f){ anc[u][0]=f;pos[u]=++id;idx[id]=u;size[u]=1; for(int k=1;k<=18;k++) anc[u][k]=anc[anc[u][k-1]][k-1]; dep[u]=dep[f]+1; insert(rt[f],rt[u],a[u],30); for(int i=head[u];i;i=e[i].nxt){ int v=e[i].to; if(v==f)continue; dfs(v,u);size[u]+=size[v]; } return; } inline int LCA(int i,int j){ if(dep[i]<dep[j])swap(i,j); for(int k=18;k>=0;k--){ if(dep[anc[i][k]]>=dep[j])i=anc[i][k]; } if(i==j)return i; for(int k=18;k>=0;k--){ if(anc[i][k]!=anc[j][k])i=anc[i][k],j=anc[j][k]; } return anc[i][0]; } int main(){ n=read(),q=read(); for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<n;i++){ int u=read(),v=read(); add(u,v);add(v,u); } dfs(1,0); for(int i=1;i<=n;i++)insert(rt[i+n],rt[i+n+1],a[idx[i]],30); for(int i=1;i<=q;i++){ int op=read(); if(op==1){ int x=read(),y=read(); int l=pos[x],r=l+size[x]-1; printf("%d ",query(rt[l+n],rt[r+n+1],y,30)); }else{ int x=read(),y=read(),z=read(); int lca=LCA(x,y),f=anc[lca][0]; printf("%d ",max(query(rt[f],rt[x],z,30),query(rt[f],rt[y],z,30))); } } return 0; }
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++