[JSOI2018]潜入行动

发表于 分类于

题目链接

链接

题解

刚高考完，好久没做这么水的树形DP了，手有点生qaq。

设 $f_{i,j,k,l}$ 表示以 $i$ 为子树中，用了 $j$ 次监听，$i$ 是否使用监听，$i$ 是否被监听的方案数。

子树在 $i$ 处合并，分情况讨论即可。

注意空间限制，只能开下int。

时间复杂度 $O(nk)$。

证明：对于 $i$ 的儿子 $son$，要与 $i$ 合并，那么时间复杂度为 $O(\min{siz_i,k}\times \min{siz_{son},k})$。

当 $siz_i,siz_{son}$ 大于 $k$ 时，只有 $\frac{n}{k}$ 个点，总时间复杂度 $O(nk)$。

当 $siz_{son}$ 小于 $k$ 时，考虑 $son$ 子树中的每个点，他一直合并上去时，需要花费的时间不会超过 $k$，总时间复杂度 $O(nk)$。

于是总复杂度还是 $O(nk)$ 。证毕。

程序

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
#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
#define CASET fo(___,1,read())
const ll mod=1e9+7;
const int N=100003;
const int M=103;
inline ll Add(ll x,ll y)
{
	x+=y;
	if(x>=mod) return x-mod;
	return x;
}
inline ll Mul(ll x,ll y)
{
	return x*y%mod;
}
int n,k;
vector<int> adj[N];
int f[N][M][2][2],g[M][2][2],siz[N];
inline void add(int x,int y)
{
	adj[x].pb(y); adj[y].pb(x);
}
void dfs(int u,int pre)
{
	f[u][0][0][0]=1;
	f[u][1][1][0]=1;
	siz[u]=1;
	for(auto v:adj[u])
		if(v^pre)
		{
			dfs(v,u);
			int l=min(k,siz[u]);
			siz[u]+=siz[v];
			fo(i,0,l)
				fo(j,0,1)
					fo(k,0,1)
						g[i][j][k]=f[u][i][j][k],f[u][i][j][k]=0;
			fo(i,0,l)
				fo(j,0,min(siz[v],k-i))
				{
					f[u][i+j][0][0]=Add(f[u][i+j][0][0],Mul(g[i][0][0],f[v][j][0][1]));
					f[u][i+j][0][1]=Add(f[u][i+j][0][1],Mul(g[i][0][1],(f[v][j][0][1]+f[v][j][1][1])));
					f[u][i+j][0][1]=Add(f[u][i+j][0][1],Mul(g[i][0][0],f[v][j][1][1]));
					f[u][i+j][1][0]=Add(f[u][i+j][1][0],Mul(g[i][1][0],(f[v][j][0][0]+f[v][j][0][1])));
					f[u][i+j][1][1]=Add(f[u][i+j][1][1],Mul(g[i][1][1],(f[v][j][0][0]+f[v][j][0][1])%mod+(f[v][j][1][0]+f[v][j][1][1])%mod));
					f[u][i+j][1][1]=Add(f[u][i+j][1][1],Mul(g[i][1][0],(f[v][j][1][0]+f[v][j][1][1])));
				}
		}
}

int main()
{
	n=read(); k=read();
	ff(i,1,n) add(read(),read());
	dfs(1,0);
	printf("%lld",Add(f[1][k][0][1],f[1][k][1][1]));
	return 0;
}