Problem

Luogu

Solution

首先思考一个问题，我们怎么求得一个路径的异或起来的和呢？

没错，快速一点的方法就是前缀和，利用异或前缀和可以解决一些问题

异或有个性质 a\otimes b\otimes b=a，所以 s_{u,v}=s_u\otimes s_v\otimes s_{lca}\otimes s_{lca}=s_u\otimes s_v。

所以 \sum_{i,j \in (u,v)} s_i \otimes s_j

那么你已经掌握了暴力解法了，接下来就是优化！

首先想一个问题

对于一个路径 (x,y)，我们应该怎么搞出他的答案呢？

看到 0 \leq w \leq 2^{10}-1，你是不是有些顿悟捏？

嗯，那么熟练点，拆二进制位对于求解异或似乎是一个很方便的做法

然后我们针对某个二进制位研究：

对一个路径，s_x \otimes s_y，才会对答案有 1 的贡献

那么要求对于每一个对答案有贡献的点对，应该是一个为 1 一个为 0，即数值不同。

那么这一位对答案的贡献应为 1 的个数乘上 0 的个数乘上 (1<<i)。

好了，我们大概知道这么求了，对于树上路径当然是使用树剖拉（你用 LCT 我没意见）

然后呢建立一个线段树，记录下每一个点到根的异或前缀和，然后再保存下 1 的个数以及 0 的个数

由于是储存异或前缀和，所以一个点被改变，他的子树也会被改变。

那么，我们对于线段树的每一个点的改变，都是 sum - 目前的个数，换句话来说就是翻转子树内 0，1 的个数。

Code

#include <bits/stdc++.h>
using namespace std;
#define il inline
#define cl(a, b) memset(a, b, sizeof(a))
typedef long long ll;
typedef unsigned long long ull;

#define N 30300

struct Edge
{
    int val, v, next;
} e[N << 1];
int cnt = 1, head[N];

il void edd(int u, int v, int val)
{
    e[cnt].val = val;
    e[cnt].v = v;
    e[cnt].next = head[u];
    head[u] = cnt++;
    return;
}

ll W[N];
int n, q;

struct Tree
{
    int l, r, f;
    ll sum;
};
#define ls(x) (x << 1)
#define rs(x) ((x << 1) | 1)
struct SeG
{
    Tree t[N << 2];
    il void down(int x)
    {
        if (t[x].f == 0) return;
        t[ls(x)].sum = t[ls(x)].r - t[ls(x)].l + 1 - t[ls(x)].sum;
        t[rs(x)].sum = t[rs(x)].r - t[rs(x)].l + 1 - t[rs(x)].sum;

        t[ls(x)].f ^= 1;
        t[rs(x)].f ^= 1;

        t[x].f = 0;
        return;
    }

    il void pushup(int x)
    {
        t[x].sum = t[ls(x)].sum + t[rs(x)].sum;
        return;
    }

    void build(int x, int l, int r, int tt)
    {
        t[x].l = l, t[x].r = r;
        if (l == r)
        {
            t[x].sum = (W[l] >> tt) & 1;
            return;
        }
        int mid = (l + r) >> 1;
        build(ls(x), l, mid, tt);
        build(rs(x), mid + 1, r, tt);
        pushup(x);
        return;
    }

    void change(int x, int l, int r)
    {
        if (t[x].l > r || t[x].r < l) return;
        if (t[x].l >= l && t[x].r <= r)
        {
            t[x].sum = t[x].r - t[x].l + 1 - t[x].sum;
            t[x].f ^= 1;
            return;
        }
        down(x);
        change(ls(x), l, r), change(rs(x), l, r);
        pushup(x);
        return;
    }

    ll ask(int x, int l, int r)
    {
        if (t[x].l > r || t[x].r < l) return 0;
        if (t[x].l >= l && t[x].r <= r) return t[x].sum;
        down(x);
        return ask(ls(x), l, r) + ask(rs(x), l, r);
    }
};

struct TLC
{
    int size[N], dep[N], fa[N], son[N], eg[N];
    ll  val[N];
    int top[N], id[N], rev[N], tot;

    SeG tree[10];

    void dfs1(int u, int f)
    {
        dep[u] = dep[f] + 1;
        size[u] = 1;
        fa[u] = f;
        for (int i = head[u]; i; i = e[i].next)
        {
            int v = e[i].v;
            if (f == v) continue;
            eg[v] = e[i].val;
            val[v] = val[u] ^ e[i].val;
            dfs1(v, u);
            size[u] += size[v];
            if (size[v] > size[son[u]] || !son[u]) son[u] = v;
        }
    }

    void dfs2(int u, int t)
    {
        top[u] = t;
        id[u] = ++tot;
        rev[tot] = u;
        if (!son[u]) return;
        dfs2(son[u], t);
        for (int i = head[u]; i; i = e[i].next)
        {
            int v = e[i].v;
            if (v == fa[u] || son[u] == v) continue;
            dfs2(v, v);
        }
    }

    void change(int u, int v, int w)
    {
        if (dep[u] < dep[v]) swap(u, v);
        for (int i = 0; i <= 9; i++)
        {
            if (((eg[u] >> i) & 1) ^ ((w >> i) & 1)) tree[i].change(1, id[u], id[u] + size[u] - 1);
        }
        eg[u] = w;
        return;
    }

    int LCA(int u, int v)
    {
        while (top[u] != top[v])
        {
            if (dep[top[u]] < dep[top[v]]) swap(u, v);
            u = fa[top[u]];
        }
        return dep[u] < dep[v] ? u : v;
    }

    ll Pask(int u, int v, int tt)
    {
        if (dep[u] < dep[v]) swap(u, v);
        int lca = LCA(u, v), gs = 0, tot = 0;
        tot = dep[u] + dep[v] - 2 * dep[lca] + 1;
        while (top[u] != top[v])
        {
            if (dep[top[u]] < dep[top[v]]) swap(u, v);
            gs += tree[tt].ask(1, id[top[u]], id[u]);
            u = fa[top[u]];
        }
        if (dep[u] > dep[v]) swap(u, v);
        gs += tree[tt].ask(1, id[u], id[v]);
        return gs * (tot - gs);
    }

    ll ask(int u, int v)
    {
        ll ans = 0;
        for (int i = 0; i <= 9; i++)
            ans += Pask(u, v, i) * (1 << i);
        return ans;
    }
} a;

#define in(x) x = read()
il int read()
{
    int v = 1, x = 0;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-') v = -1;
        ch = getchar();
    }
    while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
    return x * v;
}

int main()
{
    in(n), in(q);
    for (int i = 1; i < n; i++)
    {
        int u, v, w;
        in(u), in(v), in(w);
        edd(u, v, w);
        edd(v, u, w);
    }
    a.dfs1(1, 0);
    a.dfs2(1, 1);
    for (int i = 1; i <= n; i++) W[a.id[i]] = a.val[i];
    for (int i = 0; i <= 9; i++) a.tree[i].build(1, 1, n, i);
    for (int i = 0; i < q; i++)
    {
        int op;
        in(op);
        switch (op)
        {
        case 1:
        {
            int u, v;
            in(u), in(v);
            printf("%lld\n", a.ask(u, v));
            break;
        }
        case 2:
        {
            int u, v, w;
            in(u), in(v), in(w);
            a.change(u, v, w);
            break;
        }
        }
    }
}