题目

喵星系有$n$个星球，星球以及星球间的航线形成一棵树。
从星球$a$到星球$b$要花费$[dis(a,b)XorM]$秒。dis(a,b)表示$a,b$间的航线长度
求星球$i$到其他所有星球花费的时间之和。

输入

第一行包含两个正整数$n，M$
接下来$n−1$行，每行$3$个正整数$a,b,c$表示$a，b$之间的航线长度为$c$

输出

$n$行，每行一个整数，表示星球i到其他所有星球花费的时间之和。

样例

input
4 0
1 2 1
1 3 2
1 4 3
output
6
8
10
12

数据规模

测试点编号	N	M
1	6	0
2	100	5
3	2000	9
4	50000	0
5	50000	0
6	50000	1
7	50000	6
8	100000	10
9	100000	13
10	100000	15

答案不超过2×10^9。

题解

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;const int Max = 1e5+10;
struct psx{int y, v, nxt;} e[Max<<1];
int tot, n, M, hea[Max];
ll dp[Max], path[Max][16], sche[16];
//path表示i到其他点，后四位为j的路径条数
//sche后四位状态为j的向上的路径条数inline void insert(int x, int y, int v) {e[++tot].nxt = hea[x];e[tot].y = y;e[tot].v = v;hea[x] = tot;
}inline void init(){scanf("%d%d", &n, &M);for(int i = 1, a, b, c; i < n; i++) {scanf("%d%d%d", &a, &b, &c);insert(a, b, c);insert(b, a, c);}
}void dfs1(int x, int fa) {path[x][0] = 1;for(int i = hea[x]; i; i = e[i].nxt) {int y = e[i].y, z = e[i].v;if(y == fa) continue;dfs1(y, x);dp[x] += dp[y];for(int j = 0; j < 16; j++) {path[x][(j+z)%16] += path[y][j];dp[x] += 1LL*path[y][j] * z;}}
}//子树void dfs2(int x, int fa) {for(int i = hea[x]; i; i = e[i].nxt) {int y = e[i].y, z = e[i].v;if(y == fa) continue;int sz = 0;memset(sche, 0, sizeof sche);for(int j = 0; j < 16; j++) {sche[(j+z)%16] += path[x][j] - path[y][((j-z)%16+16)%16];sz += path[y][j];}dp[y] = dp[x] + (n - sz*2) * z;for(int j = 0; j < 16; j++) path[y][j] += sche[j];dfs2(y, x);}
}//换根void calc() {//后四位for(int i = 1; i <= n; i++) {--path[i][0];//自己减自己for(int j = 0; j < 16; j++) {int val = (j ^ M) - j;dp[i] += 1LL * path[i][j] * val;}}
}inline void work(){dfs1(1, 0);dfs2(1, 0);calc();
}inline void outo(){for(int i = 1; i <= n; i++)printf("%d\n", dp[i]);
}int main() {init();work();outo();return 0;
}