牛客练习赛58 F.XOR TREE

题目链接
思路：给的一条路径，统计所有被奇数个路径包含的点的异或和。
路径上的点显然是深度连续递增的点，那么我们根据两端深度的奇偶情况就可以知道路径上的哪些点是有贡献的。
把路径剖出来，用bit维护一下异或和即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
int n,m,a[N],sz[N],df[N],to[N],son[N],fa[N],cnt,dep[N];
vector<int>v[N];
void dfs1(int o,int pre){
  int s=-1;sz[o]=1;fa[o]=pre;dep[o]=dep[pre]+1;
  for(auto k:v[o]){
    if(k!=pre){
      dfs1(k,o);
      sz[o]+=sz[k];
      if(sz[k]>s){
        s=sz[k];son[o]=k;
      }
    }
  }
}
void dfs2(int o,int t){
  to[o]=t;
  df[o]=++cnt;
  if(son[o])dfs2(son[o],t);
  for(auto k:v[o]){
    if(k==fa[o]||k==son[o])
      continue;
    dfs2(k,k);
  }
}
int T[3][N];
void add(int p,int d,int x){
  for(;p<N;p+=p&-p)T[x][p]^=d;
}
int get(int p,int x){
  int res=0;
  for(;p;p-=p&-p)res^=T[x][p];
  return res;
}
int main() {
  scanf("%d%d",&n,&m);
  for(int i=1;i<=n;i++)scanf("%d",a+i);
  for(int i=1;i<n;i++){
    int s,t;
    scanf("%d%d",&s,&t);
    v[s].pb(t);
    v[t].pb(s);
  }
  dfs1(1,0);
  dfs2(1,1);
  for(int i=1;i<=n;i++){
    add(df[i],a[i],dep[i]%2);
    add(df[i],a[i],2);
  }
  for(int i=1;i<=m;i++){
    int ope,l,r;
    scanf("%d",&ope);
    if(ope==1){
      scanf("%d%d",&l,&r);
      add(df[l],a[l]^r,dep[l]%2);
      add(df[l],a[l]^r,2);
      a[l]=r;
    }else{
      scanf("%d%d",&l,&r);
      int sta;
      if(dep[l]%2!=dep[r]%2)sta=2;
      else{
        if(dep[l]&1)sta=0;
        else sta=1;
      }
      int ans=0;
      while(to[l]!=to[r]){
        if(df[l]<df[r])swap(l,r);
        ans^=get(df[to[l]]-1,sta)^get(df[l],sta);
        l=fa[to[l]];
      }
      if(df[l]<df[r])swap(l,r);
      ans^=get(df[r]-1,sta)^get(df[l],sta);
      printf("%d\n",ans);
    }
  }
  return 0;
}