甚么神仙题啊……
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iterator>
#include <utility>
#define int long long
using namespace std;
const int N = 3e4 + 10;
int n;
int q;
int dep[N];
int sz[N];
int fa[N];
int len[N];
int rk[N];
int top[N];
int dfs_order[N];
int son[N];
int cnt;
int w[N];
int qwq[N];
int a[N];
vector <pair <int, int> > zz[N];
struct Node
{
int l;
int r;
int lazy;
int sum[15];
int x0;
int x1;
int cnt0[15];
int cnt1[15];
Node ()
{
l = 0;
r = 0;
memset (sum, 0, sizeof sum);
memset (cnt0, 0, sizeof cnt0);
memset (cnt1, 0, sizeof cnt1);
lazy = 0;
x0 = 0;
x1 = 0;
}
~Node ()
{
l = 0;
r = 0;
memset (sum, 0, sizeof sum);
memset (cnt0, 0, sizeof cnt0);
memset (cnt1, 0, sizeof cnt1);
lazy = 0;
x0 = 0;
x1 = 0;
}
void color(int p)
{
lazy ^= (1 << p);
if (sum[p] == 1)
{
sum[p] = 0;
}
else
{
sum[p] = 1;
}
x0 = x0 - cnt0[p] + cnt1[p];
x1 = x1 - cnt1[p] + cnt0[p];
swap (cnt0[p], cnt1[p]);
}
void init(int p)
{
l = p;
r = p;
for (int i = 0; i < 10; i ++)
{
if (qwq[p] & (1 << i))
{
sum[i] = 1;
cnt1[i] = 1;
}
else
{
cnt0[i] = 1;
}
}
for (int i = 0; i < 10; i ++)
{
if (sum[i])
{
x1 ++;
}
else
{
x0 ++;
}
}
lazy = 0;
}
int query()
{
int x = 0;
for (int i = 9; ~i; i --)
{
x = x << 1 | sum[i];
}
return x;
}
}
z[N << 2];
Node operator + (const Node &lhs, const Node &rhs)
{
Node ans;
ans.l = lhs.l;
ans.r = rhs.r;
for (int i = 0; i < 10; i ++)
{
ans.sum[i] = lhs.sum[i] + rhs.sum[i];
}
for (int i = 0; i < 10; i ++)
{
ans.cnt0[i] = lhs.cnt0[i] + rhs.cnt0[i];
}
for (int i = 0; i < 10; i ++)
{
ans.cnt1[i] = lhs.cnt1[i] + rhs.cnt1[i];
}
ans.lazy = 0;
ans.x0 = lhs.x0 + rhs.x0;
ans.x1 = lhs.x1 + rhs.x1;
return ans;
}
void build(int l, int r, int rt)
{
if (l == r)
{
z[rt].init(l);
return ;
}
int mid = l + r >> 1;
build(l, mid, rt << 1);
build(mid + 1, r, rt << 1 | 1);
z[rt] = z[rt << 1] + z[rt << 1 | 1];
}
void dfs1(int now, int fat = -1)
{
dep[now] = dep[fa[now]] + 1;
sz[now] = 1;
for (auto &[u, v] : zz[now])
{
if (u != fat)
{
a[u] = v;
w[u] = w[now] ^ v;
fa[u] = now;
dfs1(u, now);
sz[now] += sz[u];
if (sz[u] > sz[son[now]])
{
son[now] = u;
}
}
}
}
void dfs2(int now, int h, int fat = -1)
{
cnt ++;
dfs_order[cnt] = now;
rk[now] = cnt;
qwq[cnt] = w[now];
top[now] = h;
len[h] ++;
int p = -1;
for (auto &[u, v] : zz[now])
{
if (u != fat)
{
if (p == -1)
{
p = u;
}
else
{
if (sz[u] > sz[p])
{
p = u;
}
}
}
}
if (p == -1)
{
return ;
}
dfs2(p, h, now);
for (auto &[u, v] : zz[now])
{
if (p != u)
{
if (u != fat)
{
dfs2(u, u, now);
}
}
}
}
int lca(int x, int y)
{
while (top[x] != top[y])
{
if (dep[top[x]] < dep[top[y]])
{
swap(x, y);
}
x = fa[top[x]];
}
if (dep[x] < dep[y])
{
return x;
}
else
{
return y;
}
}
void push_lazy(int rt)
{
int la = z[rt].lazy;
for (int i = 0; i < 10; i ++)
{
if (la & (1 << i))
{
z[rt << 1].color(i);
z[rt << 1 | 1].color(i);
}
}
z[rt].lazy = 0;
}
void modify(int l, int r, int rt, int nowl, int nowr, int value)
{
if (nowl <= l)
{
if (r <= nowr)
{
z[rt].color(value);
return ;
}
}
int mid = l + r >> 1;
push_lazy(rt);
if (nowl <= mid)
{
modify(l, mid, rt << 1, nowl, nowr, value);
}
if (mid < nowr)
{
modify(mid + 1, r, rt << 1 | 1, nowl, nowr, value);
}
z[rt] = z[rt << 1] + z[rt << 1 | 1];
}
void modify_tree(int p, int c)
{
for (int i = 0; i < 10; i ++)
{
if ((a[p] ^ c) >> i & 1)
{
modify(1, n, 1, rk[p], rk[p] + sz[p] - 1, i);
}
}
a[p] = c;
}
int query(int l, int r, int rt, int nowl, int nowr)
{
if (nowl <= l)
{
if (r <= nowr)
{
return z[rt].query();
}
}
push_lazy(rt);
int ans = 0;
int mid = l + r >> 1;
if (nowl <= mid)
{
ans ^= query(l, mid, rt << 1, nowl, nowr);
}
if (mid < nowr)
{
ans ^= query(mid + 1, r, rt << 1 | 1, nowl, nowr);
}
return ans;
}
int query_link(int p1, int p2)
{
int ans = 0;
while (true)
{
if (top[p1] == top[p2])
{
if (dep[p1] > dep[p2])
{
swap(p1, p2);
}
ans ^= query(1, n, 1, rk[p1], rk[p2]);
break;
}
else
{
if (dep[top[p1]] < dep[top[p2]])
{
swap (p1, p2);
}
int p3 = top[p1];
ans ^= query(1, n, 1, rk[p3], rk[p1]);
p1 = fa[p3];
}
}
return ans;
}
Node que(int l, int r, int rt, int nowl, int nowr)
{
if (nowl <= l)
{
if (r <= nowr)
{
return z[rt];
}
}
int mid = l + r >> 1;
push_lazy(rt);
if (nowr <= mid)
{
return que(l, mid, rt << 1, nowl, nowr);
}
if (mid < nowl)
{
return que(mid + 1, r, rt << 1 | 1, nowl, nowr);
}
return que(l, mid, rt << 1, nowl, nowr) + que(mid + 1, r, rt << 1 | 1, nowl, nowr);
}
int query(int x, int y)
{
int c1[20] = {0};
int c0[20] = {0};
while (top[x] != top[y])
{
if (dep[top[x]] < dep[top[y]])
{
swap (x, y);
}
Node orz = que(1, n, 1, rk[top[x]], rk[x]);
for (int i = 0; i < 10; i ++)
{
c1[i] += orz.cnt1[i];
c0[i] += orz.cnt0[i];
}
x = fa[top[x]];
}
if (rk[x] > rk[y])
{
swap (x, y);
}
Node orz = que(1, n, 1, rk[x], rk[y]);
for (int i = 0; i < 10; i ++)
{
c1[i] += orz.cnt1[i];
c0[i] += orz.cnt0[i];
}
int ans = 0;
for (int i = 0; i < 10; i ++)
{
ans = ans + (1 << i) * c1[i] * c0[i];
}
return ans;
}
signed main()
{
cin >> n >> q;
for (int i = 1; i < n; i ++)
{
int u, v, w;
cin >> u >> v >> w;
zz[u].push_back(make_pair(v, w));
zz[v].push_back(make_pair(u, w));
}
dfs1(1);
dfs2(1, 1);
build(1, n, 1);
while (q --)
{
int opt;
cin >> opt;
if (opt == 1)
{
int u, v;
cin >> u >> v;
cout << query(u, v) << '\n';
}
else
{
int u, v, w;
cin >> u >> v >> w;
int c = query_link(u, v);
if (dep[u] < dep[v])
{
modify_tree(v, w);
}
else
{
modify_tree(u, w);
}
}
}
return 0;
}