小a认为一棵"平衡树"的定义为:一个 n 个点(从1到n编号)、n-1 条边、任意两点间存在唯一简单路径,且点数 n >= k 的连通块。
现在给你一棵有 n 个节点的树(保证 n >= k),你想删去其中的某些边,使得剩下的若干个连通块都满足是平衡树(即每个连通块的点数都 >= k)。求删边的方案总数。两个方案不同当且仅当存在某条边在一个方案里被删、在另一个方案里没被删。答案对 1000000007 取模。
第1行:两个整数 n 和 k(1 <= k <= n <= 1000),以空格分隔。
接下来 n-1 行,每行两个整数 u、v,表示一条连接 u 和 v 的树边。
输出一个整数,表示满足条件的删边方案总数对 1000000007 取模的结果。
4 2 1 2 2 3 3 4
2
树形 DP:以 1 为根,设 f[u][s] 表示在 u 的子树内,"包含 u 的那个尚未闭合的连通块"大小为 s、且其余已闭合的连通块都 >= k 的方案数。合并儿子 v 时有两种选择:断开 u-v(此时 v 的开放块必须 >= k,贡献为 Σ f[v][t], t>=k)或保留(两块合并,大小相加)。最终答案为 Σ f[1][s], s>=k。用类似树上背包的方式合并,复杂度 O(n*n)。