原题：「East!_XI」第一个问题 2015年10月4日hzwer改写了题面

「题目背景」

小奇采的矿实在太多了，它准备在喵星系建个矿石仓库。令它无语的是，喵星系的货运飞船引擎还停留在上元时代！

「问题描述」

喵星系有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

「数据范围」

序号 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

题解

出题人18357：

算法1：

不会写函数的小伙伴们，我们只需要写个floyd，就有10分啦！

算法2：

在算法1的基础上，我们对每条边处理一下xor，就有20分啦！

算法3：

简单的树形DP，或者你会nlogn的dij，处理完每个点到其它点的最短路后再加上xor，那么这样就有30分啦！

算法4：

第4、5个点无需xor，那么我们树形DP扫一个节点与其它所有节点的路径长度之和，可以合并信息，最终均摊O(1)，50分到手。

算法5：

第6个点xor 1，那么我们树形DP到一个点时记录有多少个0，多少个1，然后每当一条路径到2，那部分就再记录一个值，60分到手。

算法6：

如果你第6个点都过了，却没有满分，笨死啦！

一样的嘛，就是原来的“0”、“1”、大于等于2变成了0~16么~~

满了。