重构了 过了(
鬼知道我原来错哪了(逃
```cpp
#include<bits/stdc++.h>
#define ls(id) (id<<1)
#define rs(id) (id<<1|1)
#define ll long long
#define N 30004
#define W 10
using namespace std;
int n,q,cnt;
struct side{
int v,w;
};
vector<side>g[N];
struct data{
int c0[W],c1[W];
}emp;
data operator+(const data &x,const data &y){
data res;
for(int i=0;i<W;i++){
res.c0[i]=x.c0[i]+y.c0[i];
res.c1[i]=x.c1[i]+y.c1[i];
}
return res;
}
struct node{
int l,r,tag;
data dx;
}st[N<<2];
int w_[N],sum[N];
int dep[N],fa[N],siz[N],son[N];
int num[N],wt[N],top[N];
inline int read(){
int x=0;
char ch=getchar();
while(!isdigit(ch))
ch=getchar();
while(isdigit(ch)){
x=(x<<1)+(x<<3)+(ch&15);
ch=getchar();
}
return x;
}
void dfs1(int id,int f){
dep[id]=dep[f]+1;
fa[id]=f,siz[id]=1;
int maxn=0;
for(side i:g[id]){
if(i.v==f)continue;
w_[i.v]=i.w;
sum[i.v]=sum[id]^i.w;
dfs1(i.v,id);
if(siz[i.v]>maxn)
maxn=siz[i.v],son[id]=i.v;
siz[id]+=siz[i.v];
}
}
void dfs2(int id,int tp){
num[id]=++cnt;
wt[cnt]=sum[id];
top[id]=tp;
if(!son[id])return;
dfs2(son[id],tp);
for(side i:g[id])
if(i.v!=son[id]&&i.v!=fa[id])dfs2(i.v,i.v);
}
inline void push_up(int id){
st[id].dx=st[ls(id)].dx+st[rs(id)].dx;
}
inline void make_tag(int id,int tag){
st[id].tag^=tag;
for(int i=0;i<W;i++)
if(tag&(1<<i))swap(st[id].dx.c0[i],st[id].dx.c1[i]);
}
inline void push_down(int id){
if(!st[id].tag)return;
make_tag(ls(id),st[id].tag);
make_tag(rs(id),st[id].tag);
st[id].tag=0;
}
void build(int id,int l,int r){
st[id]={l,r};
if(l==r){
for(int i=0;i<W;i++)
if(wt[l]&(1<<i))
st[id].dx.c1[i]=1;
else
st[id].dx.c0[i]=1;
return;
}
int mid=(l+r)>>1;
build(ls(id),l,mid);
build(rs(id),mid+1,r);
push_up(id);
}
void update(int id,int l,int r,int val){
if(st[id].l>r||st[id].r<l)return;
if(l<=st[id].l&&st[id].r<=r){
make_tag(id,val);
return;
}
push_down(id);
update(ls(id),l,r,val);
update(rs(id),l,r,val);
push_up(id);
}
data query(int id,int l,int r){
if(st[id].l>r||st[id].r<l)return emp;
if(l<=st[id].l&&st[id].r<=r)return st[id].dx;
push_down(id);
return query(ls(id),l,r)+query(rs(id),l,r);
}
data path_query(int u,int v){
data res=emp;
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])swap(u,v);
res=res+query(1,num[top[u]],num[u]);
u=fa[top[u]];
}
if(num[u]>num[v])swap(u,v);
return res+query(1,num[u],num[v]);
}
int main(){
int u,v,w,op;
data ij;
ll ans;
n=read(),q=read();
for(int i=1;i<n;i++){
u=read(),v=read(),w=read();
g[u].push_back({v,w});
g[v].push_back({u,w});
}
dfs1(1,0);
dfs2(1,1);
build(1,1,n);
while(q--){
op=read(),u=read(),v=read();
if(op==1){
ij=path_query(u,v),ans=0;
for(int i=0;i<W;i++)
ans+=1ll*ij.c0[i]*ij.c1[i]<<i;
printf("%lld\n",ans);
}
else{
if(fa[u]==v)swap(u,v);
w=read();
update(1,num[v],num[v]+siz[v]-1,w_[v]^w);
w_[v]=w;
}
}
}
```
by 233L @ 2022-12-26 22:08:20