题目

Source

http://acm.hdu.edu.cn/showproblem.php?pid=5909

Description

Byteasar has a tree T with n vertices conveniently labeled with 1,2,...,n. Each vertex of the tree has an integer value vi.

The value of a non-empty tree T is equal to v1⊕v2⊕...⊕vn, where ⊕ denotes bitwise-xor.

Now for every integer k from [0,m), please calculate the number of non-empty subtree of T which value are equal to k.

A subtree of T is a subgraph of T that is also a tree.

Input

The first line of the input contains an integer T(1≤T≤10), denoting the number of test cases.

In each test case, the first line of the input contains two integers n(n≤1000) and m(1≤m≤2¹⁰), denoting the size of the tree T and the upper-bound of v.

The second line of the input contains n integers v1,v2,v3,...,vn(0≤vi<m), denoting the value of each node.

Each of the following n−1 lines contains two integers ai,bi, denoting an edge between vertices ai and bi(1≤ai,bi≤n).

It is guaranteed that m can be represent as 2^k, where k is a non-negative integer.

Output

For each test case, print a line with m integers, the i-th number denotes the number of non-empty subtree of T which value are equal to i.

The answer is huge, so please module 10⁹+7.

Sample Input

2
4 4
2 0 1 3
1 2
1 3
1 4
4 4
0 1 3 1
1 2
1 3
1 4

Sample Output

3 3 2 3
2 4 2 3

分析

题目大概说给一棵结点有权的树，定义一个连通块的价值为其所有结点点权异或和，问这棵树有几个价值为[0,m)的子图。

• dp[u][m]表示以u结点为根的子树中，价值为m且包含u结点的子图的个数
• 通过依次与各个儿子的状态值合并转移，合并利用FWT加速。。时间复杂度不明觉厉。。

代码

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define M 1000000007LL

#define MAXN 1111

struct Edge{

    int v,next;

}edge[MAXN<<1];

int NE,head[MAXN];

void addEdge(int u,int v){

    edge[NE].v=v; edge[NE].next=head[u]; head[u]=NE++;

}

void FWT(long long *a,int n){

    for(int d=1; d<n; d<<=1){

        for(int m=d<<1,i=0; i<n; i+=m){

            for(int j=0; j<d; ++j){

                long long x=a[i+j],y=a[i+j+d];

                a[i+j]=(x+y)%M;

                a[i+j+d]=(x-y+M)%M;

            }

        }

    }

}

void UFWT(long long *a,int n){

    for(int d=1; d<n; d<<=1){

        for(int m=d<<1,i=0; i<n; i+=m){

            for(int j=0; j<d; ++j){

                long long x=a[i+j],y=a[i+j+d];

                a[i+j]=(x+y)*500000004LL%M;

                a[i+j+d]=(x-y+M)*500000004LL%M;

            }

        }

    }

}

void Convolution(long long *a,long long *b,int n){

    FWT(a,n); FWT(b,n);

    for(int i=0; i<n; ++i){

        a[i]=a[i]*b[i]%M;

    }

    UFWT(a,n);

}

int n,m;

int val[MAXN];

long long d[MAXN][1111];

long long A[1111],B[1111];

void dfs(int u,int fa){

    d[u][val[u]]=1;

    for(int i=head[u]; i!=-1; i=edge[i].next){

        int v=edge[i].v;

        if(v==fa) continue;

        dfs(v,u);

        memcpy(A,d[u],sizeof(A));

        memcpy(B,d[v],sizeof(B));

        Convolution(A,B,m);

        for(int i=0; i<m; ++i){

            d[u][i]+=A[i];

            d[u][i]%=M;

        }

    }

}

int main(){

    int t;

    scanf("%d",&t);

    while(t--){

        scanf("%d%d",&n,&m);

        for(int i=1; i<=n; ++i){

            scanf("%d",val+i);

        }

        NE=0;

        memset(head,-1,sizeof(head));

        int a,b;

        for(int i=1; i<n; ++i){

            scanf("%d%d",&a,&b);

            addEdge(a,b);

            addEdge(b,a);

        }

        memset(d,0,sizeof(d));

        dfs(1,1);

        for(int i=0; i<m; ++i){

            long long ans=0;

            for(int j=1; j<=n; ++j){

                ans+=d[j][i];

                ans%=M;

            }

            if(i) putchar(' ');

            printf("%I64d",ans);

        }

        putchar('\n');

    }

    return 0;

}