小奇采的矿实在太多了，它准备在喵星系建个矿石仓库。令它无语的是，喵
星系的货运飞船引擎还停留在上元时代！
喵星系有 n 个星球，星球以及星球间的航线形成一棵树。
从星球 a 到星球 b 要花费[dis(a,b) Xor M]秒。（dis（a,b）表示 ab 间的
航线长度，Xor 为位运算中的异或）
为了给仓库选址，小奇想知道，星球 i（1<=i<=n）到其它所有星球花费的
时间之和。
第一行包含两个正整数 n，M。
接下来 n-1 行，每行 3 个正整数 a,b,c，表示 a，b 之间的航线长度为 c。
n 行，每行一个整数，表示星球 i 到其它所有星球花费的时间之和。
4 0
1 2 1
1 3 2
1 4 3
6
8
10
12
一：暴力50分
1.对小于2000的点,直接跑n遍Dij就可以过.
2.可以发现3,4两点异或值是0：
假如v是u的儿子,他们之间边长为w,tot1[i]表示i子树内所有节点到i的距离和,tot2[i]表示所有非i子树内的节点到i的距离和.那么有：
tot1[u]=sigma{tot1[v]}+(size[u]-1)w(=sigma{tot1[v]+size[v]w})
tot2[v]=tot2[u]+(n-size[v])w(=tot2[u]+(n-size[u]+size[u]-size[v])w)
直接dfs计算.
二:正解
异或值!=0:
那么如果有异或的话,肿么办呢?
可以发现异或的值M很小,最大只有15.所以这么小的异或值可以来搞些什么呢?
16的二进制是10000,可以发现,只有后四位会受到异或的影响.
我们知道对每两点间的dis,只有mod16的部分会被异或影响,那么我们用树dp求每个点到其他所有点的dis值的mod16和1~16的各有多少个 和 >16部分（/ 16）的值.
于是设f[i][j]为i到其它点,后4位状态为j的路径条数
显然列出：
f[u][0]=1
f[u][(j+w)%16]+=f[v][j]
这还只算了子树
f[v][(j+w)%16]+=(f[u][j]-f[v][((j-w)%16+16)%16])
解释一下，u这个点的所有f[u][j]除去v的方案再加入v，等于把v的方案
从子树补到整颗树
#pragma GCC target("f16c")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse3","sse2","sse")
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize("no-stack-protector")
#pragma GCC target("avx","sse4","sse4.1","sse4.2","ssse3")
#include<bits/stdc++.h>
#define re register
using namespace std;
typedef long long ll;
const double eps=1e-7;
const int INF=1e9;
const int N=1e5+50;
/*
思路:
一：暴力50分
1.对小于2000的点,直接跑n遍Dij就可以过.
2.可以发现3,4两点异或值是0：
假如v是u的儿子,他们之间边长为w,tot1[i]表示i子树内所有节点到i的距离和,tot2[i]表示所有非i子树内的节点到i的距离和.那么有：
tot1[u]=sigma{tot1[v]}+(size[u]-1)*w(=sigma{tot1[v]+size[v]*w})
tot2[v]=tot2[u]+(n-size[v])*w(=tot2[u]+(n-size[u]+size[u]-size[v])*w)
直接dfs计算.
二:正解
异或值!=0:
那么如果有异或的话,肿么办呢?
可以发现异或的值M很小,最大只有15.所以这么小的异或值可以来搞些什么呢?
16的二进制是10000,可以发现,只有后四位会受到异或的影响.
我们知道对每两点间的dis,只有mod16的部分会被异或影响,那么我们用树dp求每个点到其他所有点的dis值的mod16和1~16的各有多少个 和 >16部分（/ 16）的值.
于是设f[i][j]为i到其它点,后4位状态为j的路径条数
显然列出：
f[u][0]=1
f[u][(j+w)%16]+=f[v][j]
这还只算了子树
f[v][(j+w)%16]+=(f[u][j]-f[v][((j-w)%16+16)%16])
解释一下，u这个点的所有f[u][j]除去v的方案再加入v，等于把v的方案
从子树补到整颗树
*/
int n,m;
int tot;
int dis[N];
int Pow[20];
int head[2*N];
int f[N][16],g[N],t[16];
struct Kano {
int u,v,w;
} kano[2*N];
inline void add(int x,int y,int z) {
kano[++tot].u=head[x];
kano[tot].v=y;
kano[tot].w=z;
head[x]=tot;
return ;
}
inline void dfs1(int now,int fa) {
for(int i=head[now]; i; i=kano[i].u) {
int to=kano[i].v;
int pay=kano[i].w;
if(to!=fa) {
dfs1(to,now);
g[now]+=g[to]+pay/16;
f[now][pay%16]++;
for(int j=0; j<16; j++) {
int k=j+pay;
g[now]+=k/16*f[to][j];
f[now][k%16]+=f[to][j];
/*
g是now到子节点中路径大于16的个数.
f存的是子节点中余数为j的个数.
*/
}
}
}
}
inline void dfs2(int now,int fa) {
for(int i=head[now]; i; i=kano[i].u) {
int to=kano[i].v;
int pay=kano[i].w;
if(to!=fa) {
int sum=g[now]-g[to];
/*
now节点其它子树大于16的个数.
t代表儿子这一块的f.
*/
for(int j=0; j<16; j++) {
int k=j+pay;
sum-=k/16*f[to][j];
t[k%16]=f[now][k%16]-f[to][j];
}
t[pay%16]--;
g[to]+=sum;
f[to][pay%16]++;
for(int j=0; j<16; j++) {
int k=j+pay;
g[to]+=k/16*t[j];
f[to][k%16]+=t[j];
}
dfs2(to,now);
}
}
}
int main() {
freopen("warehouse.in","r",stdin);
freopen("warehouse.out","w",stdout);
scanf("%d%d",&n,&m);
int a,b,c;
for(int i=1; i<n; i++) {
scanf("%d%d%d",&a,&b,&c);
add(a,b,c),add(b,a,c);
}
dfs1(1,0);
dfs2(1,0);
for(int i=1; i<=n; i++) {
ll res=g[i]*16;
for(int j=0; j<16; j++) res+=(j^m)*f[i][j];
printf("%lld\n",res);
}
return 0;
}原文：https://www.cnblogs.com/Fast-Bird/p/11850486.html