A6596. 「SDOI / SXOI2022」小 N 的独立集
编程题
省选/NOI-
知识点
题目描述
小 N 喜欢出最大权独立集问题。
有一天，他接到了一系列的出题任务，于是他顺手出了一系列最大权独立集问题。
为了同时给这一系列题目造数据，小 N 生成了一个 $n$ 个点的树，并选定了一个正整数 $k$。这样每生成一组数据时，他只需要对于每个点，随机生成一个在 $1 \sim k$ 之间的整数点权，就可以生成一个新的最大独立集问题。
小 N 把这些题给了他的好朋友，小 Ω。小 Ω 表示，这些题太多太乱了，他打算把所有的 $k^n$ 道题归类处理。一个自然的想法就是按答案（也就是最大权独立集中的点的权值之和）分类，显然这些最大权独立集问题的答案一定在 $1 \sim nk$ 之间，所以小 Ω 只需要将所有题目按照答案分成 $nk$ 类进行管理就行了。
在小 N 正式开始出题之前，小 Ω 先要算出每一类题目具体有多少道。稍加估计之后小 Ω 很快意识到自己并没有《诗云》中描述的那种存储器，于是断然拒绝了小 N 关于“先把所有可能的题目造好再慢慢分类统计数量”的建议，然后悲剧地意识到自己并不会计算这些数字。
他想叫你帮他解决这个问题，还说如果你成功解决了这个问题，那么在小 N 出那些最大权独立集问题的时候，他会帮你提交一份标程代码。
有一天，他接到了一系列的出题任务，于是他顺手出了一系列最大权独立集问题。
为了同时给这一系列题目造数据，小 N 生成了一个 $n$ 个点的树，并选定了一个正整数 $k$。这样每生成一组数据时，他只需要对于每个点，随机生成一个在 $1 \sim k$ 之间的整数点权，就可以生成一个新的最大独立集问题。
小 N 把这些题给了他的好朋友，小 Ω。小 Ω 表示，这些题太多太乱了，他打算把所有的 $k^n$ 道题归类处理。一个自然的想法就是按答案（也就是最大权独立集中的点的权值之和）分类，显然这些最大权独立集问题的答案一定在 $1 \sim nk$ 之间，所以小 Ω 只需要将所有题目按照答案分成 $nk$ 类进行管理就行了。
在小 N 正式开始出题之前，小 Ω 先要算出每一类题目具体有多少道。稍加估计之后小 Ω 很快意识到自己并没有《诗云》中描述的那种存储器，于是断然拒绝了小 N 关于“先把所有可能的题目造好再慢慢分类统计数量”的建议，然后悲剧地意识到自己并不会计算这些数字。
他想叫你帮他解决这个问题，还说如果你成功解决了这个问题，那么在小 N 出那些最大权独立集问题的时候，他会帮你提交一份标程代码。
输入格式
第一行，$2$ 个正整数 $n, k$。
接下来 $n-1$ 行，每行 $2$ 个正整数 $u_i$, $v_i$，描述一条连接点 $u_i$ 和 $v_i$ 的边，保证这些边构成一棵树。
接下来 $n-1$ 行，每行 $2$ 个正整数 $u_i$, $v_i$，描述一条连接点 $u_i$ 和 $v_i$ 的边，保证这些边构成一棵树。
输出格式
$nk$ 行，每行一个整数，第 $i$ 个整数表示在所有可能的题目中，最大权独立集大小为 $i$ 的有多少道，答案对 $10^9+7$ 取模。
输入输出样例
输入 #1
4 2 1 2 2 3 2 4
输出 #1
0 0 2 6 6 2 0 0
说明/提示
- 对于 $15 \%$ 的数据，$n \leq 8$;
- 对于 $30 \%$ 的数据，$n \leq 30$；
- 对于 $50 \%$ 的数据，$n \leq 100$；
- 对于另外 $10 \%$ 的数据，$k=1$；
- 对于另外 $15 \%$ 的数据，$k=2$；
- 对于 $100 \%$ 的数据，$n \leq 1000, k \leq 5 , u_{i}, v_{i} \leq n$。
最大权独立集问题是指：选择一个点集，使得任意两个被选择的点都没有边直接相连，并且使得所有被选择的点的点权之和最大。
- 对于 $30 \%$ 的数据，$n \leq 30$；
- 对于 $50 \%$ 的数据，$n \leq 100$；
- 对于另外 $10 \%$ 的数据，$k=1$；
- 对于另外 $15 \%$ 的数据，$k=2$；
- 对于 $100 \%$ 的数据，$n \leq 1000, k \leq 5 , u_{i}, v_{i} \leq n$。
最大权独立集问题是指：选择一个点集，使得任意两个被选择的点都没有边直接相连，并且使得所有被选择的点的点权之和最大。