Tree Cutting

题目连接：

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≤210), 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 2k, 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 109+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

Hint

题意

给你一棵树，然后问你，里面有多少个连通块的异或和为j

题解：

树形DP去做，然后我们考虑转移，用fwt去进行优化就好了

至于为什么这么变换的。。。。

俺也不是很清楚：http://picks.logdown.com/posts/179290-fast-walsh-hadamard-transform

代码

#include<bits/stdc++.h>

using namespace std;

const int mod = 1e9+7;

const int inv = (mod+1)/2;

const int maxn = 3005;

int n,m,ans[maxn],val[maxn];

vector<int> E[maxn];

long long dp[maxn][maxn],tmp[maxn],a[maxn],b[maxn];

void fwt(long long *aa,int l,int r)

{

    if(r-l==1)return;

    int mid=(l+r)/2;

    fwt(aa,l,mid);

    fwt(aa,mid,r);

    int len=mid-l;

    for(int i=l;i<mid;i++)

    {

        long long x1=aa[i];

        long long x2=aa[i+len];

        aa[i]=(x1+x2)%mod;

        aa[i+len]=(x1-x2+mod)%mod;

    }

}

void ifwt(long long *aa,int l,int r)

{

    if(r-l==1)return;

    int mid=(l+r)/2;

    int len=mid-l;

    for(int i=l;i<mid;i++)

    {

        long long y1=aa[i];

        long long y2=aa[i+len];

        aa[i]=(y1+y2)*inv%mod;

        aa[i+len]=((y1-y2+mod)%mod*inv)%mod;

    }

    ifwt(aa,l,mid);

    ifwt(aa,mid,r);

}

void solve(long long *aa,long long *bb)

{

    memcpy(a,aa,sizeof(long long)*m);

    memcpy(b,bb,sizeof(long long)*m);

    fwt(a,0,m);

    fwt(b,0,m);

    memset(tmp,0,sizeof(tmp));

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

        tmp[i]=a[i]*b[i]%mod;

    ifwt(tmp,0,m);

}

void dfs(int x,int f)

{

    memset(dp[x],0,sizeof(dp[x]));

    dp[x][val[x]]=1;

    for(int i=0;i<E[x].size();i++){

        int v=E[x][i];

        if(v==f)continue;

        dfs(v,x);

        solve(dp[x],dp[v]);

        for(int j=0;j<m;j++)(dp[x][j]+=tmp[j])%=mod;

    }

    for(int i=0;i<m;i++)(ans[i]+=dp[x][i])%=mod;

}

void solve()

{

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

    for(int i=0;i<m;i++)ans[i]=0;

    for(int i=1;i<=n;i++)scanf("%d",&val[i]),E[i].clear();

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

    {

        int x,y;

        scanf("%d%d",&x,&y);

        E[x].push_back(y);

        E[y].push_back(x);

    }

    dfs(1,0);

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

    {

        if(i==0)printf("%d",ans[i]);

        else printf(" %d",ans[i]);

    }

    printf("\n");

}

int main()

{

    int t;scanf("%d",&t);

    while(t--)solve();

    return 0;

}

巴特西

HDU 5909 Tree Cutting 动态规划快速沃尔什变换

Tree Cutting

题目连接：

Description

Input

Output

Sample Input

Sample Output

Hint

题意

题解：

代码

最新文章

热门文章

巴特西

HDU 5909 Tree Cutting 动态规划 快速沃尔什变换

Tree Cutting

题目连接：

Description

Input

Output

Sample Input

Sample Output

Hint

题意

题解：

代码

最新文章

热门文章

HDU 5909 Tree Cutting 动态规划快速沃尔什变换