← 返回题目列表

AtCoder · arc165_e

E. 随机隔离

中文机器翻译题面 查看原题

分数: 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