题目与标题基本无关系列。。

　　就是求路径上的异或和是否为0。。

　　可以把问题转换成求根节点到某个点的路径上的异或和。

　　每次修改只会对子树内的节点产生影响。。

　　所以dfs序+树状数组就行了。。

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 const int maxn=500023; 6 struct zs{ 7     int too,pre; 8 }e[maxn<<1];int tot,last[maxn]; 9 int tim,dfn[maxn],sz[maxn],dep[maxn],bel[maxn],fa[maxn],mx[maxn];10 int v[maxn],t[maxn];11 int i,j,k,n,m,a,b;12  13 inline void insert(int a,int b){14     e[++tot].too=b,e[tot].pre=last[a],last[a]=tot;15     e[++tot].too=a,e[tot].pre=last[b],last[b]=tot;16 }17 void dfs(int x){18     dep[x]=dep[fa[x]]+1;sz[x]=1;dfn[x]=++tim;19     for(int i=last[x];i;i=e[i].pre)if(e[i].too!=fa[x])20         fa[e[i].too]=x,dfs(e[i].too),sz[x]+=sz[e[i].too];21 }22 void dfs2(int x){23     int i;mx[x]=0;24     for(i=last[x];i;i=e[i].pre)if(e[i].too!=fa[x]&&sz[e[i].too]>sz[mx[x]])mx[x]=e[i].too;25     if(!mx[x])return;26     bel[mx[x]]=bel[x],dfs2(mx[x]);27     for(i=last[x];i;i=e[i].pre)if(e[i].too!=fa[x]&&e[i].too!=mx[x])bel[e[i].too]=e[i].too,dfs2(e[i].too);28 }29 inline int getlca(int a,int b){30     while(bel[a]!=bel[b]){31         if(dep[bel[a]]
         
          '9')rx=getchar();40     while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,rx=getchar();return ra;41 }42 inline void change(int x,int val){
    for(;x<=n;x+=x&-x)t[x]^=val;}43 inline int query(int x){44     int sm=0;45     while(x)sm^=t[x],x-=x&-x;46     return sm;47 }48 int main(){49     n=read();50     for(i=1;i<=n;i++)v[i]=read();51     for(i=1;i
          
           'Z';id=getchar());58         a=read(),b=read();59         if(id=='C')change(dfn[a],v[a]^b),change(dfn[a]+sz[a],v[a]^b),v[a]=b;60         else j=getlca(a,b),k=query(dfn[a])^query(dfn[b])^v[j],61              puts(k?"Yes":"No");62     }63     return 0;64 }
          
         
        
       
      

求lca写了链剖。。勉强挤进第一版。。