1 //BZOJ 2819  2 #include<cstdio>  3 #include<vector>  4 #include<cstring>  5 #include<cstdlib>  6 #include<iostream>  7 #include<algorithm>  8 #define rep(i,n) for(int i=0;i<n;++i)  9 #define F(i,j,n) for(int i=j;i<=n;++i) 10 #define D(i,j,n) for(int i=j;i>=n;--i) 11 #define pb push_back 12 using namespace std; 13 const int N=500010; 14 #define debug 15 int n,a[N],t[N<<2],fa[N],top[N],dep[N],son[N],size[N],tid[N],cnt=0; 16 vector<int>G[N]; 17 bool vis[N]; 18  19 #define mid (l+r>>1) 20 #define L (o<<1) 21 #define R (o<<1|1) 22 void updata(int o,int l,int r,int pos,int v){ 23     if (l==r) t[o]=v; 24     else{ 25         if (pos<=mid) updata(L,l,mid,pos,v); 26         else updata(R,mid+1,r,pos,v); 27         t[o]=t[L]^t[R]; 28     } 29 } 30  31 int ql,qr,ans=0; 32 void query_it(int o,int l,int r){ 33     if (ql<=l && qr>=r) ans^=t[o]; 34     else{ 35         if (ql<=mid) query_it(L,l,mid); 36         if (qr>mid) query_it(R,mid+1,r); 37     } 38 } 39 //segment tree end 40  41 void dfs(int x,int f,int deep){ 42     int y,maxsize=0; 43     vis[x]=1; fa[x]=f; dep[x]=deep; size[x]=1; son[x]=0; 44     rep(i,G[x].size()){ 45         y=G[x][i]; 46         if (vis[y]) continue; 47         dfs(y,x,deep+1); 48         size[x]+=size[y]; 49         if (size[y]>maxsize) maxsize=size[y],son[x]=y; 50     } 51 } 52  53 void connect(int x,int f){ 54     tid[x]=++cnt; 55     top[x]=f; vis[x]=1; 56     if (son[x]) connect(son[x],f); 57     rep(i,G[x].size()){ 58         int y=G[x][i]; 59         if (!vis[y]) connect(y,y); 60     } 61 } 62  63 void query(int x,int y){ 64     while(top[x]!=top[y]){ 65         if (dep[top[x]]<dep[top[y]]) swap(x,y); 66         ql=tid[top[x]]; qr=tid[x]; 67         query_it(1,1,n); 68         x=fa[top[x]]; 69     } 70     if (dep[x]>dep[y]) swap(x,y); 71     ql=tid[x]; qr=tid[y]; 72     query_it(1,1,n); 73 } 74  75 int main(){ 76 //    freopen("file.in","r",stdin); 77     scanf("%d",&n); 78     F(i,1,n) scanf("%d",&a[i]); 79     int x,y; 80     F(i,2,n){ 81         scanf("%d%d",&x,&y); 82         G[x].pb(y); 83         G[y].pb(x); 84     } 85     dfs(1,0,1); 86     memset(vis,0,sizeof vis); 87     connect(1,1); 88     F(i,1,n) updata(1,1,n,tid[i],a[i]); 89     int q; 90     scanf("%d",&q); 91     char cmd[3]; 92     F(i,1,q){ 93         scanf("%s%d%d",cmd,&x,&y); 94         if (cmd[0]==‘Q‘){ 95             ans=0; 96             query(x,y); 97             printf(ans ? "Yes\n" : "No\n"); 98         } 99         else updata(1,1,n,tid[x],y);100     }101     return 0;102 }

  1 /**************************************************************  2     Problem: 2819  3     User: Tunix  4     Language: C++  5     Result: Accepted  6     Time:15004 ms  7     Memory:65740 kb  8 ****************************************************************/  9   10 //BZOJ 2819 11 #include<cmath> 12 #include<cstdio> 13 #include<cstring> 14 #include<cstdlib> 15 #include<iostream> 16 #include<algorithm> 17 #define rep(i,n) for(int i=0;i<n;++i) 18 #define F(i,j,n) for(int i=j;i<=n;++i) 19 #define D(i,j,n) for(int i=j;i>=n;--i) 20 using namespace std; 21 void read(int &v){ 22     v=0; int sign=1; char ch=getchar(); 23     while(ch<‘0‘||ch>‘9‘){ if (ch==‘-‘) sign=-1; ch=getchar();} 24     while(ch>=‘0‘&&ch<=‘9‘){ v=v*10+ch-‘0‘; ch=getchar();} 25     v*=sign; 26 } 27 /******************tamplate*********************/ 28 const int N=500010; 29 int head[N],to[N<<1],next[N<<1],cnt,fa[N]; 30 void add(int x,int y){ 31     to[++cnt]=y; next[cnt]=head[x]; head[x]=cnt; 32     to[++cnt]=x; next[cnt]=head[y]; head[y]=cnt; 33 } 34 /*******************edge***********************/ 35 int n,m,dfs_clock,l[N],r[N],t[N<<1],a[N],deep[N]; 36 int st[N],top; 37 void dfs(){ 38     st[++top]=1; fa[1]=0;deep[1]=1; 39     while(top){ 40         int x=st[top]; 41         if (!l[x]){ 42             l[x]=++dfs_clock; 43             for(int i=head[x];i;i=next[i]) 44                 if (to[i]!=fa[x]){ 45                     st[++top]=to[i]; 46                     fa[to[i]]=x; 47                     deep[to[i]]=deep[x]+1; 48                 } 49         } 50         else{ 51             r[x]=++dfs_clock; 52             top--; 53         } 54     } 55 } 56 int p[N][20]; 57 void ST(){ 58     memset(p,-1,sizeof p); 59     F(i,1,n) p[i][0]=fa[i]; 60     for(int j=1;(1<<j)<=n;++j) 61         F(i,1,n) 62             if (p[i][j-1]!=-1) p[i][j]=p[p[i][j-1]][j-1]; 63 } 64 int lca(int x,int y){ 65     if (deep[x]<deep[y]) swap(x,y); 66     int k=log(deep[x])/log(2); 67     D(i,k,0) 68         if (deep[x]-(1<<i)>=deep[y]) x=p[x][i]; 69     if (x==y) return y; 70     D(i,k,0) 71         if (p[x][i]!=-1 && p[x][i]!=p[y][i]){ 72             x=p[x][i]; y=p[y][i]; 73         } 74     return p[x][0]; 75 } 76 /*****************dfs&LCA***********************/ 77 inline int lowbit(int x){return x&(-x);} 78 void update(int x,int val){ 79     for(x;x<=n*2;x+=lowbit(x)) t[x]^=val; 80 } 81 int sum(int x){ 82     int temp=0; 83     for(x;x;x-=lowbit(x)) temp^=t[x]; 84     return temp; 85 } 86 /*********************fenwick*******************/ 87 int main(){ 88     read(n); 89     F(i,1,n) read(a[i]); 90     int x,y; 91     F(i,2,n){ 92         read(x); read(y); 93         add(x,y); 94     } 95     dfs(); 96     ST(); 97     F(i,1,n) update(l[i],a[i]),update(r[i],a[i]); 98     read(m); 99     char cmd[5];100     F(i,1,m){101         scanf("%s",cmd);102         read(x); read(y);103         if (cmd[0]==‘Q‘) printf( sum(l[y])^sum(l[x])^a[lca(x,y)] ? "Yes\n" : "No\n");104         else{105             update(l[x],a[x]); update(r[x],a[x]);106             update(l[x],y); update(r[x],y);107             a[x]=y;108         }109     }110     return 0;111 }