T15683 切

题目背景

2017/11/01 T1

题目描述

给出一棵有n个结点的树,将其中的一些边切掉,使得每个节点至少有k个结点与之相连(包括自己),求方案数对786433取模的结果。

输入输出格式

输入格式:

输入第一行,包含两个正整数n,k。

接下来的 n-1 行,每行包含两个正整数 u, v,表示 u 结点 与 v 结点 有一条相连的边。

输出格式:

输出一个非负整数,表示方案数对786433取模的结果。

输入输出样例

输入样例#1: 复制

输出样例#1: 复制

输入样例#2: 复制

输出样例#2: 复制

说明

对于20%的数据:n <= 20;

另对于30%的数据:n <= 100;

另有10%的数据:k <= 100;

另有20%的数据:n <= 1000;

对于100%的数据:n <= 5000; k <= n.

树形dp,令f[i][j]表示i所在联通块大小为j的情况个数,保证i的子树内联通块除了i以外所有联通块大小 >= k

然后分为两种情况转移,连边,不连边

发现一个联通块的 >= k的个数为一定值,然后统计即可。

c++代码如下:

 

4 + 9 =