loj#P3724. 「SDOI / SXOI2022」小 N 的独立集

「SDOI / SXOI2022」小 N 的独立集

题目描述

小 N 喜欢出最大权独立集问题。

有一天,他接到了一系列的出题任务,于是他顺手出了一系列最大权独立集问题。

为了同时给这一系列题目造数据,小 N 生成了一个 nn 个点的树,并选定了一个正整数 kk。这样每生成一组数据时,他只需要对于每个点,随机生成一个在 1k1 \sim k 之间的整数点权,就可以生成一个新的最大独立集问题。

小 N 把这些题给了他的好朋友,小 Ω。小 Ω 表示,这些题太多太乱了,他打算把所有的 knk^n 道题归类处理。一个自然的想法就是按答案(也就是最大权独立集中的点的权值之和)分类,显然这些最大权独立集问题的答案一定在 1nk1 \sim nk 之间,所以小 Ω 只需要将所有题目按照答案分成 nknk 类进行管理就行了。

在小 N 正式开始出题之前,小 Ω 先要算出每一类题目具体有多少道。稍加估计之后小 Ω 很快意识到自己并没有《诗云》中描述的那种存储器,于是断然拒绝了小 N 关于“先把所有可能的题目造好再慢慢分类统计数量”的建议,然后悲剧地意识到自己并不会计算这些数字。

他想叫你帮他解决这个问题,还说如果你成功解决了这个问题,那么在小 N 出那些最大权独立集问题的时候,他会帮你提交一份标程代码。

输入格式

第一行,22 个正整数 n,kn, k

接下来 n1n-1 行,每行 22 个正整数 uiu_i, viv_i​,描述一条连接点 uiu_iviv_i 的边,保证这些边构成一棵树。

输出格式

nknk 行,每行一个整数,第 ii 个整数表示在所有可能的题目中,最大权独立集大小为 ii 的有多少道,答案对 109+710^9+7 取模。

4 2
1 2
2 3
2 4
0
0
2
6
6
2
0
0

样例 2

见附加文件中的 2.in2.ans

数据范围与提示

  • 对于 15%15 \% 的数据,n8n \leq 8;
  • 对于 30%30 \% 的数据,n30n \leq 30
  • 对于 50%50 \% 的数据,n100n \leq 100
  • 对于另外 10%10 \% 的数据,k=1k=1
  • 对于另外 15%15 \% 的数据,k=2k=2
  • 对于 100%100 \% 的数据,n1000,k5,ui,vinn \leq 1000, k \leq 5 , u_{i}, v_{i} \leq n

最大权独立集问题是指:选择一个点集,使得任意两个被选择的点都没有边直接相连,并且使得所有被选择的点的点权之和最大。