题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=5274
题意：给一棵树和叶子的值，然后有单点修改操作和询问区间操作，询问的是每一个值出现的奇偶次数，如果全是偶数次，则输出-1，否则输出那个奇数次的数，题目保证只有一个数出现奇数次。
题解：这里的题很巧妙，要想到异或的特殊性质
1 #include<cstdio> 2 #define F(i,a,b) for(int i=a;i<=b;i++) 3 #define root 1,n,1 4 #define ls l,m,rt<<1 5 #define rs m+1,r,rt<<1|1 6 7 const int N=1e5+5; 8 int t,n,m,x,y,op,an,tr[4*N],g[N],a[N],nxt[N*2],v[N*2],ed,sz[N],hs[N],fa[N],top[N],tid[N],dep[N],idx; 9 10 inline void adg(int x,int y){v[++ed]=y,nxt[ed]=g[x],g[x]=ed;} 11 //线段树部分 12 void build(int l,int r,int rt){ 13 if(l==r){tr[rt]=a[tid[l]]+1;return;} 14 int m=(l+r)>>1; 15 build(ls),build(rs); 16 tr[rt]=tr[rt<<1]^tr[rt<<1|1]; 17 } 18 19 void update(int x,int k,int l,int r,int rt){ 20 if(l==r){tr[rt]=k;return;} 21 int m=(l+r)>>1; 22 if(x<=m)update(x,k,ls); 23 else update(x,k,rs); 24 tr[rt]=tr[rt<<1]^tr[rt<<1|1]; 25 } 26 27 int query(int L,int R,int l,int r,int rt){ 28 if(L<=l&&r<=R)return tr[rt]; 29 int m=(l+r)>>1,ans=0; 30 if(L<=m)ans^=query(L,R,ls); 31 if(m<R)ans^=query(L,R,rs); 32 return ans; 33 } 34 //树链部分 35 void dfs1(int u,int pre){ 36 sz[u]=1,fa[u]=pre,hs[u]=0,dep[u]=dep[pre]+1; 37 for(int i=g[u];i;i=nxt[i]){ 38 int vv=v[i]; 39 if(vv!=pre){ 40 dfs1(vv,u); 41 if(sz[vv]>sz[hs[u]])hs[u]=vv; 42 sz[u]+=sz[vv]; 43 } 44 } 45 } 46 47 void dfs2(int u,int tp){ 48 top[u]=tp,tid[u]=++idx; 49 if(hs[u])dfs2(hs[u],tp); 50 for(int i=g[u];i;i=nxt[i]){ 51 int vv=v[i]; 52 if(vv!=fa[u]&&vv!=hs[u])dfs2(vv,vv); 53 } 54 } 55 56 int ask(int x,int y){ 57 int fx=top[x],fy=top[y],ans=0; 58 while(fx!=fy)if(dep[fx]>dep[fy])ans=query(tid[fx],tid[x],root),x=fa[fx],fx=top[x]; 59 else ans=query(tid[fy],tid[y],root),y=fa[fy],fy=top[y]; 60 if(dep[x]>dep[y])x=x^y,y=x^y,x=x^y; 61 return ans^query(tid[x],tid[y],root); 62 } 63 64 int main(){ 65 scanf("%d",&t); 66 while(t--){ 67 scanf("%d%d",&n,&m); 68 F(i,1,n)g[i]=0;ed=0,idx=0; 69 F(i,1,n-1)scanf("%d%d",&x,&y),adg(x,y),adg(y,x); 70 F(i,1,n)scanf("%d",a+i); 71 dfs1(1,0),dfs2(1,1),build(root); 72 while(m--){ 73 scanf("%d%d%d",&op,&x,&y); 74 if(op)an=ask(x,y),printf("%d ",an==0?-1:an-1); 75 else update(tid[x],y+1,root); 76 } 77 } 78 return 0; 79 }