[原创]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
附本题代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 # 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; }
