[原创]HDU 5909 Tree Cutting [树形dp+FWT]【动态规划+数学】 [原创]HDU 5909 Tree Cutting [树形dp+FWT]【动态规划+数学】
2017-07-02 19:26:37 Tabris_ 阅读数：591
博客爬取于2020-06-14 22:39:50以下为正文
版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。https://blog.csdn.net/qq_33184171/article/details/74153824
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5909
Tree Cutting Accepts: 14 Submissions: 119
问题描述
Byteasar有一棵$n$个点的无根树，节点依次编号为$1$到$n$，其中节点ii的权值为$v_i$。
定义一棵树的价值为它所有点的权值的异或和。
现在对于每个$[0,m)$的整数$k$，请统计有多少$T$的非空连通子树的价值等于$k$。
一棵树TT的连通子树就是它的一个连通子图，并且这个图也是一棵树。
输入描述
第一行包含一个正整数$T(1\leq T\leq10)$，表示测试数据的组数。
每组数据的第一行包含两个正整数$n(n\leq 1000)$和$m(1\leq m\leq 2^{10})$，分别表示树的大小以及权值的上界。
第二行包含$n$个整数$v_1,v_2,v_3,...,v_n(0\leq v_i < m)$，分别表示每个节点的权值。
接下来$n-1$行每行包含两个正整数$a_i,b_i(1\leq a_i,b_i\leq n)$，表示有一条连接$a_i$和$b_i$
输入数据保证$m$是$2$的非负整数幂。
输出描述
对于每组数据，输出一行$m$个整数，其中第$i$个整数表示价值为$i$的非空连通子树的数目。
因为答案很大，所以请模$10^9+7$后输出。
输入样例
输出样例
——————————————————————————————————————————
很容易想到树形dp
设$dp[i][j]$ 以第$i$个节点为根的联通子树异或和为$j$的数目.
转移的过程就是dp[u][i^j]+=dp[u][i]*dp[to][j];
这部分很好想到,但是复杂度却是$O(nm^2)$的.
显然超时
然后有了一个FWT这种东西,快速沃尔什变换
和FFT类似,同样是将一个$O(n^2)$的卷积运算转化为$O(n\log n)$的.
FWT是
$c[x] = \displaystyle\sum_{i ^ j=x} a[i]*b[j]$,与本题所求相同，套上去就好了
详细戳这里吧http://blog.csdn.net/liangzhaoyang1/article/details/52819835
附本题代码
# include <bits/stdc++.h> typedef long long int LL; using namespace std; # define abs(x) ((x)>0?(x):-(x)) const int N = 1e3+7; const int MOD = 1e9+7; /*****************************************************************/ vector<int>G[N]; int w[N],dp[N][(1<<10)+9],ans[(1<<10)+9],tmp[(1<<10)+9]; int n,m,len; void FWT(int 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++){ int x=a[i+j],y=a[i+j+d]; a[i+j]=(x+y)%MOD,a[i+j+d]=(x-y+MOD)%MOD; //xor:a[i+j]=x+y,a[i+j+d]=(x-y+MOD)%MOD; //and:a[i+j]=x+y; //or :a[i+j+d]=x+y; } } void UFWT(int a[],int n){ const int rev = (MOD+1)>>1; 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++){ int x=a[i+j],y=a[i+j+d]; a[i+j]=1LL*(x+y)*rev%MOD,a[i+j+d]=(1LL*(x-y)*rev%MOD+MOD)%MOD; //xor:a[i+j]=(x+y)/2,a[i+j+d]=(x-y)/2; inv //and:a[i+j]=x-y; //or :a[i+j+d]=y-x; } } void solve(int a[],int b[],int n){ FWT(a,n); FWT(b,n); for(int i=0;i<n;i++) a[i]=1LL*a[i]*b[i]%MOD; UFWT(a,n); } void dfs(int u,int f=0){ for(int i=0;i<len;i++) dp[u][i]=0; dp[u][w[u]]=1; int gz=G[u].size(); for(int i=0,to;i<gz;i++){ to=G[u][i]; if(to==f) continue; dfs(to,u); for(int i=0;i<len;i++) tmp[i]=dp[u][i]; solve(tmp,dp[to],len); for(int i=0;i<len;i++) dp[u][i]=(dp[u][i]+tmp[i])%MOD; } for(int i=0;i<len;i++) ans[i]=(ans[i]+dp[u][i])%MOD; } int main(){ int _; for(scanf("%d",&_);_;_--){ scanf("%d %d",&n,&m); memset(ans,0,sizeof(ans)); for(len=1;len<m;len<<=1); for(int i=1;i<=n;i++)scanf("%d",&w[i]); for(int i=1,u,v;i<n;i++){ scanf("%d%d",&u,&v); G[u].push_back(v); G[v].push_back(u); } dfs(1); for(int i=0;i<m-1;i++) printf("%d ",ans[i]); printf("%d\n",ans[m-1]); for(int i=1;i<=n;i++) G[i].clear(); } return 0; }
