HDU 5909 Tree Cutting（FWT+树形DP）

时间：2021-12-22 22:59:42

【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=5909

【题目大意】

　　给出一棵树，其每棵连通子树的价值为其点权的xor和，
　　问有多少连通子树的价值为1~m

【题解】

　　首先定1为根，转有根树，我们在树的每个节点保存一个权值数组，
　　表示与其连通的子树的权值，当一个子树并入其父节点时，
　　dp[x][i]=dp[x][i]+dp[x][j]*dp[y][k](j^k==i)，我们发现这是一个位运算卷积式子，
　　所以树上转移可以用fwt加速。

【代码】

#include <cstdio>

#include <algorithm>

#include <vector>

#include <cstring>

using namespace std;

typedef long long LL;

const int N=1030;

const LL mod=1e9+7;

const LL inv2=(mod+1)/2;

int val[N];

LL dp[N][N],tmp[N];

vector<int> v[N];

void FWT(LL*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++){

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

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

    }

}

void UFWT(LL*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++){

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

        a[i+j]=(x+y)%mod*inv2%mod,a[i+j+d]=(x-y+mod)%mod*inv2%mod;

    }

}

int T,n,m,x,y;

LL ans[N];

void Cal(LL *a,LL *b){

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

    FWT(a,m); FWT(b,m);

    for(int i=0;i<m;i++)a[i]=(1ll*a[i]*b[i])%mod;

    UFWT(a,m); UFWT(b,m);

    for(int i=0;i<m;i++)a[i]=(a[i]+tmp[i])%mod;

}

void DP(int x,int fx){

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

    for(auto y:v[x]){

        if(y==fx)continue;

        DP(y,x);

        Cal(dp[x],dp[y]);

    }

}

int main(){

    scanf("%d",&T);

    while(T--){

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

        for(int i=0;i<=n;i++)v[i].clear();

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

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

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

            v[x].push_back(y);

            v[y].push_back(x);

        }memset(dp,0,sizeof(dp));

        memset(ans,0,sizeof(ans));

        DP(1,1);

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

            for(int j=1;j<=n;j++)ans[i]=(ans[i]+dp[j][i])%mod;

        }for(int i=0;i<m;i++)printf(i<m-1?"%d ":"%d\n",ans[i]);

    }return 0;

}

相关文章