AT_arc165_e [ARC165E] Random Isolation
题目描述
有一棵包含 $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
输入格式
输入按以下格式从标准输入读入。
> $N$ $K$
> $A_1$ $B_1$
> $A_2$ $B_2$
> $\vdots$
> $A_{N-1}$ $B_{N-1}$
输出格式
输出答案。
说明/提示
### 限制条件
- $1\leq K