题目描述

有一棵包含 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$。第 $i$ 条边连接顶点 $A_i$ 和 $B_i$。

你需要不断进行如下操作，直到所有连通分量中包含的顶点数都不超过 $K$：

• 从所有属于某个包含至少 $K+1$ 个顶点的连通分量的顶点中，等概率随机选择一个顶点。删除以该顶点为端点的所有边。

请你计算进行操作的期望次数，并将答案对 $998244353$ 取模后输出。

期望值 $\bmod\ 998244353$ 的定义：可以证明，所求的期望值一定是有理数。在本题的约束下，若将其表示为最简分数 $\frac{P}{Q}$，则 $Q\not\equiv 0\pmod{998244353}$ 也成立。因此，存在唯一的整数 $R$ 满足 $R\times Q\equiv P\pmod{998244353},\ 0\leq R<998244353$。请输出这个 $R$。

输入格式

输入按以下格式从标准输入读入。

$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

输出

249561090

样例 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

输出

181196154

说明/提示

限制条件

• $1\leq K<N\leq 100$
• $1\leq A_i,B_i\leq N$
• 给定的图是一棵树
• 输入的所有数均为整数

样例解释 1

例如，如果第一次操作选择了顶点 $2$，则所有边都会被删除，操作后每个连通分量包含的顶点数都不超过 $2$，因此操作结束。另一方面，如果第一次操作选择了顶点 $1$，则操作后会剩下包含顶点 $2,3,4$ 的连通分量，因此需要进行第二次操作。操作次数的期望值为 $\frac{7}{4}$。

由 ChatGPT 4.1 翻译