给出树和初始结点
单点修改
询问区间内权值 对于每个②询问，如果全是偶数输出“-1”，否则输出出现奇数次的权值
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s); #define ll long long #define pb push_back #define REP(i,N) for(int i=0;i<(N);i++) #define CLR(A,v) memset(A,v,sizeof A) #define lson l,m,pos<<1 #define rson m+1,r,pos<<1|1 ////////////////////////////////// #define inf 0x3f3f3f3f3f3f3f3f const int N=100005; int t[N<<2],col[N<<2],n,m,a,b,c,s,node[N],w[N]; void up(int pos) { t[pos]=t[pos<<1]^t[pos<<1|1]; } void build(int l,int r,int pos) { if(l==r){t[pos]=w[l]; return; } int m=(l+r)>>1; build(lson);build(rson);up(pos); } int qsum(int L,int R,int l,int r,int pos) { int ans=0; if(L<=l&&r<=R)return t[pos]; int m=(l+r)>>1; if(L<=m)ans^=qsum(L,R,lson); if(R>m)ans^=qsum(L,R,rson); return ans; } void upnode(int x,int v,int l,int r,int pos) { if(l==r){t[pos]=v;return ; } int m=(l+r)>>1; if(x<=m)upnode(x,v,lson); else upnode(x,v,rson); up(pos); } int cnt,id[N],fa[N],top[N],son[N],siz[N],pos,head[N],dep[N]; struct Edge { int to,nex; }edge[N<<1]; void add(int a,int b) { edge[++pos]=Edge{b,head[a]}; head[a]=pos; } void dfs1(int x,int f) { son[x]=0; siz[x]=1; dep[x]=dep[f]+1; fa[x]=f; for(int i=head[x];i;i=edge[i].nex) { int v=edge[i].to; if(v==f)continue; dfs1(v,x); siz[x]+=siz[v]; if(siz[son[x]]<siz[v])son[x]=v; } } void dfs2(int x,int topf) { id[x]=++cnt; top[x]=topf; w[cnt]=node[x]+1; if(!son[x])return; dfs2(son[x],topf); for(int i=head[x];i;i=edge[i].nex) { int v=edge[i].to; if(v==son[x]||v==fa[x])continue; dfs2(v,v); } } int Qsum(int x,int y) { int ans=0; while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]])swap(x,y); ans^=qsum(id[top[x]],id[x],1,n,1); x=fa[top[x]]; } if(dep[x]>dep[y])swap(x,y); ans^=qsum(id[x],id[y],1,n,1); return ans; } void init() { CLR(head,0); siz[0]=dep[1]=cnt=pos=0;CLR(dep,0);CLR(son,0);CLR(siz,0); } int main() { int cas,ans;RI(cas); while(cas--) { init(); RII(n,m); rep(i,1,n-1)RII(a,b),add(a,b),add(b,a); rep(i,1,n)RI(node[i]); dfs1(1,1);dfs2(1,1);build(1,n,1); while(m--) { RIII(c,a,b); if(c==0) upnode(id[a],b+1,1,n,1); else { ans=Qsum(a,b); if(ans==0)printf("-1 "); else printf("%d ",ans-1); } } } return 0; }