【洛谷】P3401 洛谷樹

題目大意：

給一棵樹，有邊權，支援兩個操作。

（1）修改一個邊權

（2）查詢u到v的簡單路徑的所有子鍊的異或和的和

https://www.luogu.org/problemnew/show/P3401

做法：

首先這是異或，注意到滿足a^b^b = a，

要求所有子鍊的異或和，即求在(u, v)這個路徑上的任意兩點(x, y)的路徑的異或和之和

考慮處理樹上異或字首和，即sum[i] = i 異或到根，進而sum[i]^sum[j]就是 i 異或到 j

然後發現要求所有的點對，一次一次求肯定會tle，那麼考慮如何一次統計所有點對

對于某一位k，隻需要求出來所有的字首和中，這一位是0的有幾個，這一位是1的有幾個，把這兩個乘起來就是組成點對這一位是1的個數，那麼進行樹剖+線段樹即可

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <set>
#include <algorithm>
#define MAXN 30050
using 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<<], *h[MAXN];
struct node2{
    int num, num1, rev;
    node2 operator + (const node2 &x){
        node2 t;
        t.num = num + x.num;
        t.num1 = num1 + x.num1;
        t.rev = ;
        return t;
    }
}t[][MAXN<<];
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] = ;
    for(node *p = h[u]; p; p = p->next){
        if(p->v != fa[u]){
            //cout<<u<<' '<<p->v<<' '<<b[u]<<' '<<p->w<<' '<<b[p->v]<<' ';
            b[p->v] = b[u]^p->w;
            ed[p->v] = p->w;
            //cout<<b[p->v]<<endl;
            fa[p->v] = u;
            dep[p->v] = dep[u]+;
            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)&)
            t[k][u].num1 = ;
        else t[k][u].num = ;
        return;
    }
    int mid = (l+r)>>;
    build(k, u<<, l, mid); build(k, u<<|, mid+, r);
    t[k][u] = t[k][u<<] + t[k][u<<|];
    //cout<<k<<' '<<u<<' '<<l<<' '<<r<<' '<<t[k][u].num<<' '<<t[k][u].num1<<' '<<t[k][u].rev<<endl;
}
void pushdown(int k, int u){
    if(t[k][u].rev == ) return;
    //cout<<"IN "<<k<<' '<<u<<endl;
    swap(t[k][u<<].num, t[k][u<<].num1);
    swap(t[k][u<<|].num, t[k][u<<|].num1);
    t[k][u<<].rev ^= ;
    t[k][u<<|].rev ^= ;
    t[k][u].rev = ;
}
void rev(int k, int u, int l, int r, int tl, int tr){
    if(tl <= l && r <= tr){
        swap(t[k][u].num, t[k][u].num1);
        t[k][u].rev ^= ;
        return;
    }
    int mid = (l+r)>>;
    pushdown(k, u);
    if(tl <= mid) rev(k, u<<, l, mid, tl, tr);
    if(mid < tr) rev(k, u<<|, mid+, r, tl, tr);
    t[k][u] = t[k][u<<] + t[k][u<<|];
}
void change(int u, int w){
    for(int i = ; i <= ; i++){
        if(((w^ed[u])>>i)&)
            rev(i, , , n, id[u], id[u]+size[u]-);
    }
    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)>>;
    pushdown(k, u);
    node2 ret; ret.num = ret.num1 = ; 
    if(tl <= mid) ret = ret + query(k, u<<, l, mid, tl, tr);
    if(mid < tr) ret = ret + query(k, u<<|, mid+, r, tl, tr);
    //cout<<k<<' '<<u<<' '<<l<<' '<<r<<' '<<t[k][u].num<<' '<<t[k][u].num1<<endl;
    return ret;
}
long long Query(int u, int v){
    long long ret = ;
    int U = u, V = v;
    for(int i = ; i <= ; i++){
        u = U, v = V;
        //cout<<i<<endl;
        node2 res; res.num = res.num1 = ;
        while(top[u] != top[v]){
            if(dep[top[u]] < dep[top[v]]) swap(u, v);
            res = res + query(i, , , n, id[top[u]], id[u]);
            //cout<<id[top[u]]<<' '<<id[u]<<' '<<res.num<<' '<<res.num1<<endl;
            u = fa[top[u]];
        }
        if(dep[u] > dep[v]) swap(u, v);
        res = res + query(i, , , n, id[u], id[v]);
        //cout<<id[u]<<' '<<id[v]<<' '<<res.num<<' '<<res.num1<<endl;
        ret += (LL<<i)*res.num*res.num1;
    }
    return ret;
}
int main(){
    //freopen("1.in", "r", stdin);
    //freopen("1.out", "w", stdout);
    int opt, u, v, w;
    scanf("%d%d", &n, &q);
    for(int i = ; i < n; i++) scanf("%d%d%d", &u, &v, &w), addedge(u, v, w);
    dep[] = ;
    dfs1();
    dfs2(, );
    //for(int i = ; i <= n; i++) cout<<dep[i]<<' ';cout<<endl;
    for(int i = ; i <= ; i++) build(i, , , n);
    while(q--){
        scanf("%d%d%d", &opt, &u, &v);
        if(opt == ){
            printf("%lld\n", Query(u, v));
        }
        else{
            scanf("%d", &w);
            if(u != fa[v]) swap(u, v);
            change(v, w);
        }
    }
    return ;
}