「HDU5909」Tree Cutting - 树上依赖背包+FWT | Bill Yang's Blog

「HDU5909」Tree Cutting - 树上依赖背包+FWT

题目大意

     给出一个$n$个点的无根树,在树上选出一个连通块,问选出连通块异或和为$i$的方案数$\bmod10^9+7$是多少?


题目分析

首先无根树转有根树。
然后考虑做依赖背包,儿子可以转移到父亲,也可以断掉不转移。
构造每个结点的生成函数$f(i,z)$,设当前点为$u$,儿子为$v$,用$\oplus$代表卷积。

初始化时$f(u)=z^{v_u}$。

使用FWT优化异或卷积即可。


代码

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {
if(x=='-')bj=-1;
x=getchar();
}
while(isdigit(x)) {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=1005,maxm=1<<10;
const int mod=1e9+7,inv2=5e8+4;
struct FastWalshTransform {
int n;
void init(int n) {
this->n=n;
}
void transform(LL *a,LL mul) {
for(int len=2; len<=n; len<<=1) {
int mid=len>>1;
for(LL *p=a; p!=a+n; p+=len)
for(int i=0; i<mid; i++) {
LL x=p[i],y=p[mid+i];
p[i]=(x+y)*mul%mod;
p[mid+i]=(x-y+mod)*mul%mod;
}
}
}
void fwt(LL *a) {
transform(a,1);
}
void ufwt(LL *a) {
transform(a,inv2);
}
} wtf;
int t,n,m;
LL a[maxn],f[maxn][maxm],e[maxm][maxm],ans[maxm];
vector<int> edges[maxn];
void AddEdge(int x,int y) {
edges[x].push_back(y);
}
void TreeDp(int Now,int fa) {
for(int i=0; i<m; i++)f[Now][i]=e[a[Now]][i];
for(int Next:edges[Now]) {
if(Next==fa)continue;
TreeDp(Next,Now);
for(int i=0; i<m; i++)f[Now][i]=f[Now][i]*(f[Next][i]+e[0][i])%mod;
}
for(int i=0; i<m; i++)ans[i]=(ans[i]+f[Now][i])%mod;
}
void Clear() {
for(int i=1; i<=n; i++) {
edges[i].clear();
for(int j=1; j<=m; j++)f[i][j]=0;
}
for(int i=0; i<m; i++)ans[i]=0;
}
int main() {
t=Get_Int();
while(t--) {
Clear();
n=Get_Int();
m=Get_Int();
int t=1;
while(t<m)t<<=1;
wtf.init(t);
for(int i=0; i<m; i++) {
fill(e[i],e[i]+m,0);
e[i][i]=1;
wtf.fwt(e[i]);
}
for(int i=1; i<=n; i++)a[i]=Get_Int();
for(int i=1; i<n; i++) {
int x=Get_Int(),y=Get_Int();
AddEdge(x,y);
AddEdge(y,x);
}
TreeDp(1,0);
wtf.ufwt(ans);
for(int i=0; i<m; i++)printf("%lld%c",ans[i],i==m-1?'\n':' ');
}
return 0;
}
0%