HDU5274 Dylans loves tree（树链剖分）很巧的点权更新

Dylans有一棵N个点的树。每个点有点权。树上节点标号为1∼N。
他得到了Q个询问，形式如下：
①0 x y：把第x个点的点权修改为y。
②1 x y：对于x∼y路径上的每一种点权，是否都出现偶数次？
保证每次询问的路径上最多只有一种点权的出现次数是奇数次。1≤N,Q≤100000, 点权A[i]∈N，且都 ≤100000

第一行一个正整数T表示数据组数（T≤3且最多只有一组数据N>1000）
第一行两个数N、Q表示树的点数和询问个数。
接下来N−1行每行一对数(x,y)表示树上的一条边。
接下来一行N个数表示每个点的点权。
接下来Q行每行三个数(opt,x,y)表示询问。

对于每个②询问，如果全是偶数输出“-1"，否则输出出现奇数次的权值。

1
3 2
1 2
2 3
1 1 1
1 1 2
1 1 3

-1
1

hack数据里N和Q必须小于等于10000，且对于读入的每一行末尾不应该有多余的空格。

解题：

#pragma comment(linker,"/STACK:1024000000,1024000000")
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<map>
using namespace std;
const int N = 100005;
#define LL __int64
struct EDG{int to,next;
}edg[N*2];
int eid,head[N];
int fath[N],deep[N],top[N],num[N],son[N],p[N],pos;
void init(){pos=0; eid=0;memset(head,-1,sizeof(head));
}
void addEdg(int u,int v){edg[eid].to=v; edg[eid].next=head[u]; head[u]=eid++;edg[eid].to=u; edg[eid].next=head[v]; head[v]=eid++;
}
void dfs(int u,int pre,int d){fath[u]=pre; num[u]=1; deep[u]=d; son[u]=-1;for(int i=head[u]; i!=-1; i=edg[i].next){int v=edg[i].to;if(v==pre)continue;dfs(v,u,d+1);num[u]+=num[v];if(son[u]==-1||num[son[u]]<num[v])son[u]=v;}
}
void getpos(int u,int root){top[u]=root;p[u]=++pos;if(son[u]==-1)return ;getpos(son[u],root);for(int i=head[u]; i!=-1; i=edg[i].next){int v=edg[i].to;if(son[u]==v||v==fath[u])continue;getpos(v,v);}
}
int root[N*3];  //记录当前区间内所有值的xor
int a[N];
void build(int l,int r,int k){if(l==r){root[k]=a[l];return ;}int m=(l+r)>>1;build(l,m,k<<1);build(m+1,r,k<<1|1);root[k]=root[k<<1]^root[k<<1|1];
}
void updata(int l,int r,int k,int id,int vule){if(l==r){root[k]=vule;return ;}int m=(l+r)>>1;if(id<=m)updata(l,m,k<<1,id,vule);elseupdata(m+1,r,k<<1|1,id,vule);root[k]=root[k<<1]^root[k<<1|1];
}
int query(int l,int r,int k,int L,int R){if(L<=l&&r<=R){return root[k];}int m=(l+r)>>1 , ans=0;if(L<=m)ans^= query(l,m,k<<1,L,R);if(m<R)ans^=query(m+1,r,k<<1|1,L,R);return ans;
}
void swp(int &aa,int &bb){int tt=aa; aa=bb; bb=tt;
}
int Operat(int u,int v){int fu=top[u] , fv=top[v],ans=0;while(fu!=fv){if(deep[fu]<deep[fv]){swp(fu,fv); swp(u,v);}ans^= query(1,pos,1,p[fu],p[u]);u=fath[fu]; fu=top[u];}if(deep[u]>deep[v])swp(u,v);ans^=query(1,pos,1,p[u],p[v]);return ans;
}int main()
{int T,n,q,val[N],u,v;scanf("%d",&T);while(T--){scanf("%d%d",&n,&q);init();for(int i=1; i<n; i++){scanf("%d%d",&u,&v);addEdg(u,v);}for(int i=1; i<=n; i++){scanf("%d",&val[i]);val[i]++;}dfs(1,1,1);getpos(1,1);for(int i=1; i<=n; i++)a[p[i]]=val[i];build(1,pos,1);while(q--){int op,x,y;scanf("%d%d%d",&op,&x,&y);if(op==0)updata(1,pos,1,p[x],y+1);//加1else{printf("%d\n",Operat(x,y)-1);//减1}}}return 0;
}