参考博客

https://www.cnblogs.com/Mychael/p/9255572.html

https://www.cnblogs.com/cjyyb/p/9065611.html

题意：给定一棵无根树，统计所有子树的异或和的个数。

dp[u][i],表示u为根的数，xor值得到i的方案数

显然，每次合并就是两个dp    dp值做xor   xor卷积

利用FWT优化异或卷积

然后被卡常

链式前向星更快

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define swap(a,b) (a^=b^=a^=b)
const ll maxn=2050;
const ll mod= 1e9+7;
ll inv2;
ll a[1<<17],b[1<<17],c[1<<17],N;
inline ll read()
{
    ll x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<3)+(x<<1)+ch-'0';
        ch=getchar();
    }
    return x*f;
}
inline void FWT_xor(ll *a,ll f)
{
    register ll i,j,p,k;
    for(i=1; i<N; i<<=1)for(p=i<<1,j=0; j<N; j+=p)for(k=0; k<i; ++k)
            {
                ll X=a[j+k],Y=a[i+j+k];
                a[j+k]=(X+Y)%mod;
                a[i+j+k]=(X+mod-Y)%mod;
                if(f==-1)a[j+k]=1ll*a[j+k]*inv2%mod,a[i+j+k]=1ll*a[i+j+k]*inv2%mod;
            }
}
ll qpow(ll a,ll n)
{
    ll ans=1;
    while(n)
    {
        if(n&1)
            ans=ans*a%mod;
        a=a*a%mod;
        n>>=1;
    }
    return ans;
}
ll dp[maxn][maxn];
vector<ll>v[maxn];
ll val[maxn];
void dfs(ll n,ll fa)
{
    dp[n][val[n]]=1;
    FWT_xor(dp[n],1);
    for(ll i=0; i<v[n].size(); i++)
    {
        if(v[n][i]==fa)
            continue;
        ll to=v[n][i];
        dfs(to,n);
        //FWT_xor(dp[to],1);
        for(ll j=0; j<N; j++)
        {
            dp[n][j]=dp[n][j]*(dp[to][j]+1)%mod;
        }
        //FWT_xor(dp[to],-1);
    }
    //FWT_xor(dp[n],-1);
}

int main()
{
    inv2=qpow(2,mod-2);
    ll t,n,m,x,y;
    scanf("%lld",&t);
    while(t--)
    {
        memset(dp,0,sizeof(dp));
        for(ll i=0; i<maxn; i++)
            v[i].clear();
        n=read();
        m=read();
        N=1;
        while(N<=m)N<<=1;
        for(ll i=1; i<=n; i++)
        {
            val[i]=read();
        }
        for(ll i=0; i<n-1; i++)
        {
            x=read();
            y=read();
            v[x].push_back(y);
            v[y].push_back(x);
        }
        dfs(1,0);
        for(ll i=1;i<=n;i++)
              FWT_xor(dp[i],-1);
        for(ll i=0; i<m; i++)
        {
            ll ans=0;
            for(ll j=1; j<=n; j++)
            {
                ans+=dp[j][i];
                ans%=mod;
            }
            printf("%lld",ans);
            if(i!=m-1)
                printf(" ");
        }
        printf("\n");
    }
    return 0;
}