题目大意：

给一棵树，有边权，支持两个操作。

（1）修改一个边权

（2）查询u到v的简单路径的所有子链的异或和的和

做法：

首先这是异或，注意到满足a^b^b = a，

要求所有子链的异或和，即求在(u, v)这个路径上的任意两点(x, y)的路径的异或和之和

考虑处理树上异或前缀和，即sum[i] = i 异或到根，从而sum[i]^sum[j]就是 i 异或到 j

然后发现要求所有的点对，一次一次求肯定会tle，那么考虑如何一次统计所有点对

对于某一位k，只需要求出来所有的前缀和中，这一位是0的有几个，这一位是1的有几个，把这两个乘起来就是组成点对这一位是1的个数，那么进行树剖+线段树即可

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define MAXN 30050using namespace std;/*输入格式：第一行两个正整数n和q，表示点的个数，查询和询问的总次数。接下来n-1行，每行两个正整数u、v、w，表示u和v两个点之间有一条边权为w的边。接下来q行，格式为1 u v或2 u v w。如果为1 u v操作，你需要输出u到v的路径上所有子路径经过的边的边权的xor值的和是多少；如果为2 u v w操作，你需要把u到v这条边的边权改为w，保证这条边存在。输出格式：对于每个1操作，输出答案。*/int n, q, son[MAXN], size[MAXN], dep[MAXN], fa[MAXN], top[MAXN], id[MAXN], b[MAXN], num[MAXN], ecnt, tcnt, ed[MAXN]; struct node{ int v, w; node *next; node(){} node(int _v, int _w, node *_n) { v = _v, w = _w, next = _n; }}pool[MAXN<<2], *h[MAXN];struct node2{ int num0, num1, rev; node2 operator + (const node2 &x){ node2 t; t.num0 = num0 + x.num0; t.num1 = num1 + x.num1; t.rev = 0; return t; }}t[25][MAXN<<3];inline void addedge(int u, int v, int w){ node *p1 = &pool[ecnt++], *p2 = &pool[ecnt++]; *p1 = node(v, w, h[u]), h[u] = p1; *p2 = node(u, w, h[v]), h[v] = p2;}void dfs1(int u){ size[u] = 1; for(node *p = h[u]; p; p = p->next){ if(p->v != fa[u]){ //cout<
          <<' '<
           
            v<<' '<
            
             <<' '<
             
              w<<' '<
              
               v]<<' '; b[p->v] = b[u]^p->w; ed[p->v] = p->w; //cout<
               
                v]<
                
                 v] = u; dep[p->v] = dep[u]+1; dfs1(p->v); size[u] += size[p->v]; if(size[p->v] > size[son[u]]) son[u] = p->v; } }}void dfs2(int u, int t){ id[u] = ++tcnt; num[tcnt] = b[u]; top[u] = t; if(!son[u]) return; dfs2(son[u], t); for(node *p = h[u]; p; p = p->next){ if(!id[p->v]) dfs2(p->v, p->v); }}void build(int k, int u, int l, int r){ if(l == r){ if((num[l]>>k)&1) t[k][u].num1 = 1; else t[k][u].num0 = 1; return; } int mid = (l+r)>>1; build(k, u<<1, l, mid); build(k, u<<1|1, mid+1, r); t[k][u] = t[k][u<<1] + t[k][u<<1|1]; //cout<
                 
                  <<' '<
                  <<' '<
                   
                    <<' '<
                    
                     <<' '<
                     
                      <<' '<
                      
                       <<' '<
                       
                        <
                        
                         >1; pushdown(k, u); if(tl <= mid) rev(k, u<<1, l, mid, tl, tr); if(mid < tr) rev(k, u<<1|1, mid+1, r, tl, tr); t[k][u] = t[k][u<<1] + t[k][u<<1|1];}void change(int u, int w){ for(int i = 0; i <= 10; i++){ if(((w^ed[u])>>i)&1) rev(i, 1, 1, n, id[u], id[u]+size[u]-1); } ed[u] = w;}node2 query(int k, int u, int l, int r, int tl, int tr){ if(tl <= l && r <= tr){ return t[k][u]; } int mid = (l+r)>>1; pushdown(k, u); node2 ret; ret.num0 = ret.num1 = 0; if(tl <= mid) ret = ret + query(k, u<<1, l, mid, tl, tr); if(mid < tr) ret = ret + query(k, u<<1|1, mid+1, r, tl, tr); //cout<
                         
                          <<' '<
                          <<' '<
                           
                            <<' '<
                            
                             <<' '<
                             
                              <<' '<
                              
                               <
                               
                                 dep[v]) swap(u, v); res = res + query(i, 1, 1, n, id[u], id[v]); //cout<
                                
                                 <<' '<
                                 
                                  <<' '<
                                  
                                   <<' '<
                                   
                                    <