【题意说明】
有一棵N个点的树。每个点有点权。树上节点标号为1∼N。
有Q个询问，形式如下：
(1) 0 x y：把第x个点的点权修改为y。
(2) 1 x y：对于x∼y路径上的每一种点权，是否都出现偶数次？
保证每次询问的路径上最多只有一种点权的出现次数是奇数次。
【问题分析】
由于题目中说明：保证所查询的路径上最多只有一个数会出现奇数次，这样在树链剖分后，就可以利用异或位运算来更新其值了，注意由于每个值为[0,100000]，对于值为0的处理千万要小心，可以考虑把值+1就好处理了。
【参考代码】
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define lson k<<1
#define rson k<<1|1
#define lt(i) tree[i].left
#define rt(i) tree[i].right
#define sm(i) tree[i].sum
#define tp(i) node[i].top
#define fa(i) node[i].father
#define dp(i) node[i].deep
#define sn(i) node[i].son
#define sz(i) node[i].size
#define hd(i) node[i].head
#define id(i) node[i].index
#define to(i) edge[i].to
#define nx(i) edge[i].next
const int maxN=100010;
struct Tree{
int left, right, sum;
}tree[maxN<<2];
struct Node{
int top, father, deep, head, son,
size, index;
}node[maxN];
struct Edge{
int to, next;
}edge[maxN<<1];
int n, Q, t, total;
void init();
void work();
void build(int, int, int);
void dfs1(int, int);
void dfs2(int, int);
void addedge(int, int, int);
void update(int, int, int);
int solve(int, int);
int query(int, int, int);
int main(){
scanf("%d", &t);
while(t--){
init();
work();
}
return 0;
}
void init(){
memset(tree, 0, sizeof(tree));
memset(node, 0, sizeof(node));
memset(edge, 0, sizeof(edge));
total=0;
scanf("%d%d", &n,
&Q);
for(int i=1; i<n; i++){
int x, y;
scanf("%d%d",
&x, &y);
addedge(x, y, i);
addedge(y, x, i+n);
}
dfs1(1, 1);
dfs2(1, 1);
}
void addedge(int x, int y, int k){
to(k)=y; nx(k)=hd(x); hd(x)=k;
}
void dfs1(int k, int _dp){
sz(k)=1; dp(k)=_dp;
for(int i=hd(k); i; i=nx(i)){
if(sz(to(i))) continue;
fa(to(i))=k;
dfs1(to(i), _dp+1);
sz(k)+=sz(to(i));
if(sz(sn(k))<sz(to(i)))
sn(k)=to(i);
}
}
void dfs2(int k, int _tp){
id(k)=++total; tp(k)=_tp;
if(sn(k)) dfs2(sn(k), _tp);
for(int i=hd(k); i; i=nx(i))
if(!id(to(i))) dfs2(to(i),
to(i));
}
void work(){
build(1, 1, n);
for(int i=1; i<=n; i++){
int x; scanf("%d",
&x);
update(1, id(i), x+1);
}
for(int i=0; i<Q; i++){
int flag, u, v;
scanf("%d%d%d",
&flag, &u, &v);
if(flag)
printf("%d
",
solve(u, v)-1);
else
update(1, id(u),
v+1);
}
}
void build(int k, int l, int r){
lt(k)=l; rt(k)=r;
if(l==r) return;
int mid=(l+r)>>1;
build(lson, l, mid);
if(mid<r) build(rson, mid+1, r);
}
void update(int k, int x, int v){
if(lt(k)==rt(k)){
sm(k)=v;
return;
}
if(x<=rt(lson)) update(lson, x,
v);
if(x>=lt(rson)) update(rson, x,
v);
sm(k)=sm(lson)^sm(rson);
}
int solve(int u, int v){
int f1=tp(u), f2=tp(v), ans=0;
while(f1!=f2){
if(dp(f1)<dp(f2)){
swap(u, v);
swap(f1, f2);
}
ans^=query(1, id(f1),
id(u));
u=fa(f1); f1=tp(u);
}
if(dp(u)<dp(v)) swap(u, v);
return ans^query(1, id(v), id(u));
}
int query(int k, int l, int r){
if(l<=lt(k)&&r>=rt(k))
return sm(k);
int ans=0;
if(l<=rt(lson)) ans^=query(lson,
l, r);
if(r>=lt(rson)) ans^=query(rson,
l, r);
return ans;
}