【题目背景】

小奇采的矿实在太多了，它准备在喵星系建个矿石仓库。令它无语的是，喵

星系的货运飞船引擎还停留在上元时代！

【问题描述】

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

首先考虑不异或

那么我们先算出根节点1到所有点的距离和

接下来假设2是1儿子，边为<1,2,w>，size[i]为i的子树的大小

ans[2]=ans[1]+(n-size)*w-size*w=ans[1]+(n-2*size)*w

但本题加了异或，异或不满足分配律，所以不能算出再异或

但我们发现m很小，最多也就2^4-1，也就是1111

异或只会影响后4位

于是设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的方案

从子树补到整颗树

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 using namespace std; 7 struct Node 8 { 9     int next,to,dis;10 } edge[200001];11 int num,head[100001];12 long long ans[100001],n,m,f[100001][16];13 void add(int u,int v,int dis)14 {15     num++;16     edge[num].next=head[u];17     head[u]=num;18     edge[num].to=v;19     edge[num].dis=dis;20 }21 void dfs1(int x,int pa)22 {23     int i,j;24     f[x][0]=1;25     for (i=head[x]; i; i=edge[i].next)26     {27         int v=edge[i].to;28         if (v!=pa)29         {30             dfs1(v,x);31             ans[x]+=ans[v];32             for (j=0; j<=15; j++)33                 f[x][(j+edge[i].dis)%16]+=f[v][j],ans[x]+=f[v][j]*edge[i].dis;34         }35     }36 }37 void dfs2(int x,int pa)38 {39     int i,j;40     for (i=head[x]; i; i=edge[i].next)41     {42         int v=edge[i].to;43         if (v==pa) continue;44         int a[17]= {
   0},size=0;45         for (j=0; j<=15; j++)46             a[(j+edge[i].dis)%16]+=f[x][j]-f[v][((j-edge[i].dis)%16+16)%16],size+=f[v][j];47         ans[v]=ans[x]+(n-size*2)*edge[i].dis;48         for (j=0; j<=15; j++)49             f[v][j]+=a[j];50         dfs2(v,x);51     }52 }53 int main()54 {55     int i,u,v,c,j;56     cin>>n>>m;57     for (i=1; i