题目描述
分析
(m=0) 是显然的换根 (dp)
当 (m) 不为(0),沿用换根(dp)思路
m的范围很小,加上异或是位运算
先任选一个根,(dfs)求出 到每个点的距离之和 和 距离最后四位为(0 sim 15)的方案数
与(m=0)时差不多,随便搞一下就能写出换根的变化量
代码
#include<cstdio>
#include<cstring>
inline int read(){
int x=0,fh=1;
char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxm=1e6+5,maxn=1e5+5;
int head[maxm],tot=1;
struct asd{
int to,next,val;
}b[maxm];
void ad(int aa,int bb,int cc){
b[tot].to=bb;
b[tot].next=head[aa];
b[tot].val=cc;
head[aa]=tot++;
}
int n,m,f[maxn],g[maxn],fcnt[maxn][16],gcnt[maxn][16],siz[maxn],zy[50];
void debug(int now){
printf("begin-----debug
");
printf("--------------------
");
printf("g数组 节点编号 %d
",now);
for(int i=0;i<=15;i++){
if(gcnt[now][i])printf("长度:%d 数量:%d
",i,gcnt[now][i]);
}
printf(">16的长度 %d
",g[now]);
printf("f数组 节点编号 %d
",now);
for(int i=0;i<=15;i++){
if(fcnt[now][i])printf("长度:%d 数量:%d
",i,fcnt[now][i]);
}
printf(">16的长度 %d
",f[now]);
printf("end-----debug
");
}
#define findbug printf("当前节点:%d 父亲节点:%d 儿子节点:%d
",now,fa,u)
void dfs(int now,int fa){
siz[now]=1;
for(int i=head[now];i!=-1;i=b[i].next){
int u=b[i].to;
if(u==fa) continue;
dfs(u,now);
int cs=b[i].val;
cs=(cs>>4);
cs=(cs<<4);
g[now]+=g[u]+cs*siz[u];
cs=(b[i].val&15);
for(int j=0;j<=30;j++){
zy[j]=0;
}
for(int j=0;j<=15;j++){
int nval=j+cs;
zy[nval]+=gcnt[u][j];
}
zy[cs]++;
for(int j=0;j<=30;j++){
if(j<=15){
gcnt[now][j]+=zy[j];
} else {
gcnt[now][j-16]+=zy[j];
g[now]+=zy[j]*16;
}
}
siz[now]+=siz[u];
}
}
void dfs2(int now,int fa){
if(now==1){
f[now]=g[now];
for(int i=0;i<=15;i++){
fcnt[now][i]=gcnt[now][i];
}
}
for(int i=head[now];i!=-1;i=b[i].next){
int u=b[i].to;
if(u==fa) continue;
int cs=b[i].val;
cs=(cs>>4);
cs=(cs<<4);
f[u]=f[now]-g[u]-siz[u]*cs;
f[u]+=(n-siz[u])*cs;
cs=(b[i].val&15);
for(int j=0;j<=30;j++){
zy[j]=0;
}
for(int j=0;j<=15;j++){
int nval=j+cs;
zy[nval]+=gcnt[u][j];
}
for(int j=0;j<=30;j++){
if(j<=15){
fcnt[u][j]=fcnt[now][j]-zy[j];
} else {
fcnt[u][j-16]-=zy[j];
f[u]-=zy[j]*16;
}
}
fcnt[u][cs]--;
for(int j=0;j<=30;j++){
zy[j]=0;
}
for(int j=0;j<=15;j++){
int nval=j+cs;
zy[nval]+=fcnt[u][j];
}
zy[cs]++;
for(int j=0;j<=30;j++){
if(j<=15){
fcnt[u][j]=gcnt[u][j]+zy[j];
} else {
fcnt[u][j-16]+=zy[j];
f[u]+=zy[j]*16;
}
}
f[u]+=g[u];
dfs2(u,now);
}
}
int main(){
freopen("warehouse.in","r",stdin);
freopen("warehouse.out","w",stdout);
memset(head,-1,sizeof(head));
n=read(),m=read();
int aa,bb,cc;
for(int i=1;i<n;i++){
aa=read(),bb=read(),cc=read();
ad(aa,bb,cc);
ad(bb,aa,cc);
}
dfs(1,0);
dfs2(1,0);
for(int i=1;i<=n;i++){
int nans=0;
for(int j=0;j<=15;j++){
nans=(nans+(j^m)*fcnt[i][j]);
}
printf("%d
",f[i]+nans);
}
return 0;
}