@[yah01](/space/show?uid=11560) 又不止这道题没题解
by _xcc_ @ 2016-10-09 13:40:55
ORZ
by yah01 @ 2016-10-10 15:08:28
嗯这个边权小于1023一看就知道是十棵树剖嘛对不对
by fcoaxt @ 2016-10-28 23:50:51
我这里
```cpp
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define maxn 30100
#define lans (maxn*4 -10)
#define rans (maxn*4 -100)
#define xans (maxn*4 -20)
#define yans (maxn*4 -30)
using namespace std;
struct edges{
int r,nxt,w;
}e[maxn<<1];
int head[maxn],esz;
int dep[maxn],fa[maxn],top[maxn],son[maxn],id[maxn],idsz,m,w[maxn];
long long ans[maxn<<2],pre[maxn<<2][10][2],suf[maxn<<2][10][2],yh[maxn<<2];
int dfs(int u,int f,int d){
fa[u]=f;
dep[u]=d;
int ssz=0,mxs=0,so=0;
for(int t=head[u];t;t=e[t].nxt)if(e[t].r!=f){
w[e[t].r]=e[t].w;
int a=dfs(e[t].r,u,d+1);
if(mxs<a)mxs=a,so=e[t].r;
ssz+=a;
}
son[u]=so;
return ssz+1;
}
void dfs2(int u,int tp){
id[u]=++idsz;
top[u]=tp;
if(son[u])dfs2(son[u],tp);
for(int t=head[u];t;t=e[t].nxt)
if(e[t].r!=fa[u]&&e[t].r!=son[u])
dfs2(e[t].r,e[t].r);
}
void merge(int o,int l,int r){
ans[o]=ans[l]+ans[r];
for(int i=0;i<10;++i){
int zp=(yh[l]>>i)&1;
int zs=(yh[r]>>i)&1;
ans[o]+=(suf[l][i][0]*pre[r][i][1]+suf[l][i][1]*pre[r][i][0])<<i;
// printf("[%d]",(suf[l][i][0]*pre[r][i][1]+suf[l][i][1]*pre[r][i][0])<<i);
long long a=pre[l][i][0]+pre[r][i][zp];
long long b=pre[l][i][1]+pre[r][i][!zp];
long long c=suf[r][i][0]+suf[l][i][zs];
long long d=suf[r][i][1]+suf[l][i][!zs];
pre[o][i][0]=a;
pre[o][i][1]=b;
suf[o][i][0]=c;
suf[o][i][1]=d;
}
yh[o]=yh[l]^yh[r];
}
void init(int x){
memset(pre[x],0,sizeof(pre[x]));
memset(suf[x],0,sizeof(suf[x]));
yh[x]=ans[x]=0;
}
void qsum(int x,int l,int r){
if(l>r)swap(l,r);
l+=m-1-1,r+=m+1-1;
init(xans),init(yans);
for(;l^r^1;l>>=1,r>>=1){
if(~l&1)merge(xans,xans,l^1);
if(r&1)merge(yans,r^1,yans);
}
merge(xans,xans,yans);
merge(x,xans,x);
// printf("[%d=%d]\n",x,ans[x]);
// for(int i=0;i<10;++i)printf("[%d,%d]\n",pre[x][i][1],pre[x][i][0]);
// printf("\n---------------\n");
}
void modify(int l,int a){
l+=m-1;
ans[l]=yh[l]=a;
for(int i=0;i<10;++i)
pre[l][i][0]=suf[l][i][0]=pre[l][i][1]=suf[l][i][1]=0;
for(int i=0;i<10;++i)
pre[l][i][(a>>i)&1]++,suf[l][i][(a>>i)&1]++;
for(l>>=1;l;l>>=1)merge(l,l<<1,l<<1|1);
}
long long calc(int l,int r){
ans[0]=ans[l]+ans[r];
for(int i=0;i<10;++i)
ans[0]+=(pre[l][i][0]*pre[r][i][1]+pre[l][i][1]*pre[r][i][0])<<i;
return ans[0];
}
long long query(int u,int v){
init(lans),init(rans),init(0);
int tp1=top[u],tp2=top[v],l=lans,r=rans;
while(tp1!=tp2){
if(dep[tp1]<dep[tp2])
swap(tp1,tp2),swap(u,v),swap(l,r);
// printf("[%d,%d]",u,tp1);
qsum(l,id[u],id[tp1]);
u=fa[tp1];tp1=top[u];
}
if(u==v)return calc(l,r);
if(dep[u]>dep[v])swap(u,v),swap(l,r);
qsum(r,id[son[u]],id[v]);
return calc(l,r);
}
void addedge(int u,int v,int w){
e[++esz].r=v;e[esz].nxt=head[u];head[u]=esz;
e[esz].w=w;
}
int main(){
int n,q;scanf("%d%d",&n,&q);
for(int i=1;i<n;++i){
int u,v,a;
scanf("%d%d%d",&u,&v,&a);
addedge(u,v,a);
addedge(v,u,a);
}
dfs(1,0,1);
dfs2(1,1);
for(m=1;m-2<=n;m<<=1);
for(int i=2;i<=n;++i)modify(id[i],w[i]);
for(int i=1;i<=q;++i){
int c,u,v,w;scanf("%d%d%d",&c,&u,&v);
if(c==1){
printf("%lld\n",query(u,v));
} else {
scanf("%d",&w);
modify(dep[u]<dep[v]?id[v]:id[u],w);
}
}
}
```
by lxc2006 @ 2017-03-27 19:24:55
$\mathbb {ORZ}$
$\mathtt {ORZ}$
$ORZ$
by 初日辉煌 @ 2018-07-20 10:27:16
Orz
by 忘无羡机 @ 2019-08-02 16:19:40
orz
by 可爱 @ 2020-05-25 08:47:16
考古考古
by 可爱 @ 2020-05-25 08:47:25
千克
by Balor @ 2023-06-05 21:37:03