1 #include <cstdio>  2 #include <cstring>  3 #include <cstdlib>  4 const int sizeOfPoint=500005;  5 const int sizeOfEdge=1000001;  6   7 int n, m, q;  8 int w[sizeOfPoint];  9 int f[sizeOfPoint], d[sizeOfPoint], s[sizeOfPoint]; 10 int num, idx[sizeOfPoint], top[sizeOfPoint], son[sizeOfPoint]; 11 inline char getch(); 12 inline int getint(); 13 inline void putint(int); 14  15 struct edge {int point; edge * next;}; 16 edge memory[sizeOfEdge], * port=memory; 17 edge * e[sizeOfPoint]; 18 inline edge * newedge(int, edge * ); 19 inline void link(int, int); 20  21 int tot, stack[sizeOfPoint]; 22 edge * t[sizeOfPoint]; 23 inline void dfsTree(); 24 inline void dfsChain(); 25  26 int T[sizeOfPoint<<2]; 27 inline void build(); 28 inline void updateItem(int, int); 29 inline int querySegment(int, int); 30  31 inline void swap(int & , int & ); 32 inline int queryChain(int, int); 33  34 int main() 35 { 36     char ch; 37     int u, v; 38  39     n=getint(); 40     for (int i=1;i<=n;i++) 41         w[i]=getint(); 42     for (int i=1;i<n;i++) 43     { 44         int u=getint(), v=getint(); 45         link(u, v); 46     } 47  48     dfsTree(); 49     dfsChain(); 50     build(); 51  52     q=getint(); 53     for (int i=1;i<=q;i++) 54     { 55         ch=getch(), u=getint(), v=getint(); 56  57         if (ch==‘Q‘) putint(queryChain(u, v)); 58         else updateItem(idx[u], v); 59     } 60  61     return 0; 62 } 63 inline char getch() 64 { 65     register char ch; 66     do ch=getchar(); while (ch!=‘Q‘ && ch!=‘C‘); 67     return ch; 68 } 69 inline int getint() 70 { 71     register int num=0; 72     register char ch; 73     do ch=getchar(); while (ch<‘0‘ || ch>‘9‘); 74     do num=num*10+ch-‘0‘, ch=getchar(); while (ch>=‘0‘ && ch<=‘9‘); 75     return num; 76 } 77 inline void putint(int num) 78 { 79     if (num>0) putchar(‘Y‘), putchar(‘e‘), putchar(‘s‘); 80     else putchar(‘N‘), putchar(‘o‘); 81     putchar(‘\n‘); 82 } 83 inline edge * newedge(int point, edge * next) 84 { 85     edge * ret=port++; 86     ret->point=point; ret->next=next; 87     return ret; 88 } 89 inline void link(int u, int v) 90 { 91     e[u]=newedge(v, e[u]); e[v]=newedge(u, e[v]); 92 } 93 inline void dfsTree() 94 { 95     int u; 96  97     memcpy(t, e, sizeof(e)); 98     memset(d, 0xFF, sizeof(d)); d[1]=0; 99     s[1]=1;100     for (stack[++tot]=1;tot; )101     {102         u=stack[tot];103 104         edge *& i=t[u];105         for ( ;i && d[i->point]>=0;i=i->next);106         if (i)107         {108             stack[++tot]=i->point;109             f[i->point]=u;110             d[i->point]=d[u]+1;111             s[i->point]=1;112         }113         else114         {115             if (!f[u]) break;116             s[f[u]]+=s[u];117             if (s[u]>s[son[f[u]]])118                 son[f[u]]=u;119             tot--;120         }121     }122 }123 inline void dfsChain()124 {125     int u;126 127     memcpy(t, e, sizeof(e));128     idx[1]=num=1; top[1]=1;129     for (stack[++tot]=1;tot; )130     {131         u=stack[tot];132         if (son[u] && !idx[son[u]])133         {134             stack[++tot]=son[u];135             idx[son[u]]=++num;136             top[son[u]]=top[u];137             continue;138         }139 140         edge *& i=t[u];141         for ( ;i && idx[i->point];i=i->next);142         if (i)143         {144             stack[++tot]=i->point;145             idx[i->point]=++num;146             top[i->point]=i->point;147         }148         else149         {150             if (!f[u]) break;151             tot--;152         }153     }154 }155 inline void build()156 {157     for (m=1;m<n+2;m<<=1);158     for (int i=1;i<=n;i++) T[idx[i]+m]=w[i];159     for (int i=m;i>=1;i--) T[i]=T[i<<1]^T[i<<1|1];160 }161 inline void updateItem(int i, int t)162 {163     for (T[i+=m]=t, i>>=1;i;i>>=1) T[i]=T[i<<1]^T[i<<1|1];164 }165 inline int querySegment(int l, int r)166 {167     int sum=0;168     for (l=l+m-1, r=r+m+1;l^r^1;l>>=1, r>>=1)169     {170         if (~l&1) sum^=T[l^1];171         if ( r&1) sum^=T[r^1];172     }173     return sum;174 }175 inline void swap(int & u, int & v)176 {177     int t=u; u=v; v=t;178 }179 inline int queryChain(int u, int v)180 {181     int sum=0;182     while (top[u]!=top[v])183     {184         if (d[top[u]]<d[top[v]]) swap(u, v);185         sum^=querySegment(idx[top[u]], idx[u]);186         u=f[top[u]];187     }188     if (d[u]>d[v]) swap(u, v);189     sum^=querySegment(idx[u], idx[v]);190     return sum;191 }