分数: 700 点
问题陈述
有一棵树 N 顶点编号 1 to N.The i第一条边连接顶点 A_i 和 B_i.
让我们继续执行以下操作,直到图中的每个连通分量都已 K 或更少的顶点。
- 从 N 顶点,均匀随机选择一个属于连通分量的顶点 K+1 或更多顶点。删除以所选顶点为端点的所有边。
求运算执行次数的期望值,取模 998244353.
如何打印期望值模 \text{mod }{998244353}
可以证明,求的期望值始终是有理数。另外,在该问题的约束下,还可以证明当该值表示为不可约分数时 \frac{P}{Q},我们有 Q \not \equiv 0 \pmod{998244353}。因此,有一个唯一的整数 R 这样 R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353。报告此事 R.
约束
- 1 \leq K < N \leq 100
- 1 \leq A_i,B_i \leq N
- 给定的图是一棵树。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N K
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}
输出
打印答案。
样本输入 1
4 2 1 2 2 3 2 4
示例输出 1
249561090
例如,如果第一个操作选择顶点 2,它删除所有边,之后每个连通分量不超过两个顶点,因此我们完成操作。另一方面,如果第一个操作选择顶点 1,仍然会有一个带有顶点的连通分量 2, 3,和 4,所以我们执行第二个操作。
操作次数的预期值为 \frac{7}{4}.
示例输入 2
20 10 16 8 6 2 18 3 3 12 5 1 13 9 13 19 3 11 5 13 17 6 8 14 1 16 16 20 11 15 3 10 15 4 5 18 1 7 1 17
示例输出 2
181196154