树DP 小奇的仓库(warehouse)

问题 C: 小奇的仓库(warehouse)
时间限制: 1 Sec 内存限制: 256 MB
提交: 121 解决: 30
[提交][状态]
题目描述
【题目背景】

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

【问题描述】

喵星系有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
【数据范围】略
保证答案不超过2*10^9

但看着数据范围，只能是O(N)效率。
首先想想m=0的情况：完全不用^，那么两遍dfs就解决问题了。主题思路就是一边算儿子传到父亲的，一遍算父亲传到儿子的。
再考虑m=1的情况，只要知道有多少个点到自己的距离是奇数，多少是偶数就行。也就是两遍dfs时多传个参，再根据边权是奇是偶讨论一下就好了。
我们延续上面的思路，m<=15，也就是说只会改变后四位的值，同理，我们记录后四位的值就好了，传递时，只要把后四位的值+边权，再取后四位即可。

到头来就是两遍dfs。

#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define N 100006 
int read()
{
    int sum=0,f=1;char x=getchar();
    while(x<'0'||x>'9'){if(x=='-')f=-1;x=getchar();}
    while(x>='0'&&x<='9'){sum=(sum<<1)+(sum<<3)+x-'0';x=getchar();}
    return sum*f;
}
struct road{int v,next,l;}lu[N*2];
int n,m,e,adj[N],f[N],g[N],sz[N],up[N][17];
void add(int u,int v,int l){lu[++e]=(road){v,adj[u],l};adj[u]=e;}
void dfs1(int x,int fa)
{
    sz[x]=1;
    for(int i=adj[x];i;i=lu[i].next)
    {
        int to=lu[i].v,l=lu[i].l;if(to==fa)continue;
        dfs1(to,x);
        g[x]+=g[to]+lu[i].l*sz[to];sz[x]+=sz[to];
        for(int j=0;j<16;j++)
        {
            int k=j+l;k-=k>>4<<4;
            up[x][k]+=up[to][j];
        }
        up[x][l-(l>>4<<4)]++;
    }
}
void dfs2(int x,int fa,int cnt)
{
    g[x]+=f[x];int sum=g[x],s=cnt+sz[x];
    int d[20];
    for(int i=adj[x];i;i=lu[i].next)
    {
        int to=lu[i].v,l=lu[i].l;if(to==fa)continue;
        f[to]=sum-g[to]+lu[i].l*(s-sz[to]*2);
        for(int i=0;i<16;i++)d[i]=up[x][i];
        for(int j=0;j<16;j++)
        {
            int k=j+l;k-=k>>4<<4;
            d[k]-=up[to][j];
        }
        d[l-(l>>4<<4)]--;
        for(int j=0;j<16;j++)
        {
            int k=j+l;k-=k>>4<<4;
            up[to][k]+=d[j];
        }
        up[to][l-(l>>4<<4)]++;
        dfs2(to,x,s-sz[to]);
    }
}
int main()
{   
    n=read();m=read();
    int x,y,z;
    for(int i=1;i<n;i++)
    {
        x=read();y=read();z=read();
        add(x,y,z);add(y,x,z);
    }
    dfs1(1,0);

    dfs2(1,0,0);
    /*for(int i=1;i<=n;i++)
    {
        for(int j=0;j<16;j++)
            cout<<up[i][j]<<" ";
        cout<<endl;
    }*/
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<16;j++)
        {
            int k=j^m;
            g[i]+=(k-j)*up[i][j];
        }
        printf("%d\n",g[i]);
    }
}