[原创]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
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/131072 K (Java/Others)

问题描述

Byteasar有一棵nn个点的无根树,节点依次编号为11nn,其中节点ii的权值为viv_i

定义一棵树的价值为它所有点的权值的异或和。

现在对于每个[0,m)[0,m)的整数kk,请统计有多少TT的非空连通子树的价值等于kk

一棵树TT的连通子树就是它的一个连通子图,并且这个图也是一棵树。

输入描述

第一行包含一个正整数T(1T10)T(1\leq T\leq10),表示测试数据的组数。

每组数据的第一行包含两个正整数n(n1000)n(n\leq 1000)m(1m210)m(1\leq m\leq 2^{10}),分别表示树的大小以及权值的上界。

第二行包含nn个整数v1,v2,v3,...,vn(0vi<m)v_1,v_2,v_3,...,v_n(0\leq v_i < m),分别表示每个节点的权值。

接下来n1n-1行每行包含两个正整数ai,bi(1ai,bin)a_i,b_i(1\leq a_i,b_i\leq n),表示有一条连接aia_ibib_i
的无向边。

输入数据保证mm22的非负整数幂。

输出描述

对于每组数据,输出一行mm个整数,其中第ii个整数表示价值为ii的非空连通子树的数目。

因为答案很大,所以请模109+710^9+7后输出。

输入样例
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

输出样例
3 3 2 3
2 4 2 3

——————————————————————————————————————————

很容易想到树形dp

dp[i][j]dp[i][j] 以第ii个节点为根的联通子树异或和为jj的数目.

转移的过程就是dp[u][i^j]+=dp[u][i]*dp[to][j];

这部分很好想到,但是复杂度却是O(nm2)O(nm^2)的.

显然超时

然后有了一个FWT这种东西,快速沃尔什变换

和FFT类似,同样是将一个O(n2)O(n^2)的卷积运算转化为O(nlogn)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;
}