orz，求个比较小的样例

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
template <typename type>
inline void read(type& x){
    x = 0; bool f = 0; char c = getchar();
    while(c < '0' || c > '9'){f = c == '-'; c = getchar();}
    while(c >= '0' && c <= '9'){x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}
    if(f) x = -x;
}

const int maxN = 3E4 + 5;
int head[maxN], dfn[maxN], fa[maxN], son[maxN], sz[maxN], top[maxN], depth[maxN], w[maxN], nw[maxN];
int k = 0, cnt = 0;
struct edge{
    int to, next;
    edge(int to = 0, int next = -1):to(to), next(next){}
}edges[maxN << 1];

struct seg{
    ll totS;
    int xOr, lc[10], rc[10], len;
    seg(ll totS = 0, int xOr = 0, int len = 0):totS(totS), xOr(xOr), len(len){
        memset(lc, 0, sizeof(lc));
        memset(rc, 0, sizeof(rc));
        if(xOr){
            for(int i = 0; i < 10; i++){
                if((xOr >> i) & 1){
                    lc[i] ++;
                    rc[i] ++;   
                }
            }
        }
    }
}tree[maxN << 2];

inline seg operator+ (const seg& l, const seg& r){
    if(!l.len) return r;
    if(!r.len) return l;
    seg res(0, 0, 0);
    res.xOr = l.xOr ^ r.xOr;
    res.len = l.len + r.len;
    res.totS = l.totS + r.totS;
    memcpy(res.lc, l.lc, sizeof(res.lc));
    memcpy(res.rc, r.rc, sizeof(res.rc));
    for(int i = 0; i < 10; i++){
        res.totS += 1ll * (r.lc[i] * l.len + l.rc[i] * r.len - 2 * r.lc[i] * l.rc[i]) * (1 << i);
        res.lc[i] += ((l.xOr >> i) & 1)? (r.len - r.lc[i]):r.lc[i];
        res.rc[i] += ((r.xOr >> i) & 1)? (l.len - l.rc[i]):l.rc[i];  
    }
    return res;
}

inline void add(int u, int v){
    edges[k] = edge(v, head[u]);
    head[u] = k++;
}

inline void buildTree(int s, int t, int p){
    if(s == t){
        tree[p] = seg(nw[s], nw[s], 1);
        return ;
    }
    int m = (t + s) >> 1;
    buildTree(s, m, p << 1);
    buildTree(m + 1, t, p << 1 | 1);
    tree[p] = tree[p << 1] + tree[p << 1 | 1];
}

inline void dfs1(int now, int f){
    fa[now] = f;
    depth[now] = depth[f] + 1;
    sz[now] = 1;
    int maxS = -1;
    for(int e = head[now]; ~e; e = edges[e].next){
        if(edges[e].to == f) continue;
        dfs1(edges[e].to, now);
        sz[now] += sz[edges[e].to];
        if(sz[edges[e].to] > maxS){
            maxS = sz[edges[e].to];
            son[now] = edges[e].to;
        }
    }
}

inline void dfs2(int now, int topf){
    top[now] = topf;
    dfn[now] = ++cnt;
    if(!son[now]) return;
    dfs2(son[now], topf);
    for(int e = head[now]; ~e; e = edges[e].next){
        if(dfn[edges[e].to]) continue;
        dfs2(edges[e].to, edges[e].to);
    }
}

inline void updata(int x, int v, int s, int t, int p){
    if(x == s && x == t){
        tree[p] = seg(v, v, 1);
        return ;
    }
    int m = (s + t) >> 1;
    if(m >= x){
        updata(x, v, s, m, p << 1);
    }
    else{
        updata(x, v, m + 1, t, p << 1 | 1);
    }
    tree[p] = tree[p << 1] + tree[p << 1 | 1];
}

inline seg queryRange(int l, int r, int s, int t, int p){
    if(l <= s && r >= t){
        return tree[p];
    }
    int m = (t + s) >> 1;
    seg ans(0, 0, 0);
    if(m >= l) ans = queryRange(l, r, s, m, p << 1);
    if(m < r) ans = ans + queryRange(l, r, m + 1, t, p << 1 | 1);
    return ans;
}

inline ll query(int u, int v){
    seg l(0, 0, 0), r(0, 0, 0);
    while(top[u] != top[v]){
        if(depth[top[u]] < depth[top[v]]){
            swap(u, v);
            swap(l, r);
        }
        l = queryRange(dfn[top[u]], dfn[u], 1, cnt, 1) + l;
        u = fa[top[u]];
    }
    if(dfn[u] > dfn[v]){
        swap(u, v);
        swap(l, r);
    }
    if(dfn[u] < dfn[v]){
        l = queryRange(dfn[u] + 1, dfn[v], 1, cnt, 1) + l;
    }
    ll ans = l.totS + r.totS;
    if(l.len && r.len){
        for(int i = 0; i < 10; i++){
            ans += 1ll * (r.lc[i] * l.len + l.lc[i] * r.len - 2 * r.lc[i] * l.lc[i]) * (1 << i);
        }
    }
    return ans;
}

int main(){
    int n, q, u, v, t, wei;
    read(n), read(q);
    memset(head, -1, sizeof(int) * (n + 1));
    memset(dfn, 0, sizeof(int) * (n + 1));
    memset(son, 0, sizeof(int) * (n + 1));
    memset(nw, 0, sizeof(int) * (n + 1));
    for(int i = 0; i < n - 1; i++){
        read(u), read(v), read(w[i]);
        add(u, v);
        add(v, u);
    }
    nw[1] = 0;
    depth[0] = 0;
    dfs1(1, 0);
    dfs2(1, 1);
    for(int i = 0; i < n - 1; i++){
        nw[max(dfn[edges[i << 1].to], dfn[edges[i << 1 | 1].to])] = w[i];
    }
    buildTree(1, cnt, 1);
    for(int i = 0; i < q; i++){
        read(t), read(u), read(v);
        if(t == 1){
            printf("%lld\n", query(u, v));
        }
        else{
            read(wei);
            updata(max(dfn[u], dfn[v]), wei, 1, cnt, 1);
        }
    }
    return 0;
}