E - Random Isolation Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

頂点に 1 から N の番号が付いた N 頂点からなる木があります。 i 番目の辺は頂点 A_i,B_i を結びます。

グラフの連結成分が含む頂点の数がそれぞれ K 以下になるまで以下の操作を行い続けます。

  • N 個の頂点のうち、K+1 個以上の頂点を含む連結成分に属する頂点を 1 つ一様ランダムに選ぶ。選んだ頂点を端点とする辺をすべて削除する。

操作を行う回数の期待値を \bmod 998244353 で求めてください。

期待値 \text{mod }{998244353} の定義

求める期待値は必ず有理数になることが証明できます。 また、この問題の制約のもとでは、その値を既約分数 \frac{P}{Q} で表した時、Q \not \equiv 0 \pmod{998244353} となることも証明できます。 よって、R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353 を満たす整数 R が一意に定まります。 この 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

例えば 1 回目の操作で頂点 2 が選ばれた場合、操作によって全ての辺が削除され、操作後は各連結成分が含む頂点の数はそれぞれ 2 以下であるため操作を終了します。一方 1 回目の操作で頂点 1 が選ばれた場合、操作後頂点 2,3,4 からなる連結成分が残るため、2 回目の操作が行われます。

操作回数の期待値は \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

Score : 700 points

Problem Statement

There is a tree with N vertices numbered 1 to N. The i-th edge connects vertices A_i and B_i.

Let us keep performing the following operation until each connected component of the graph has K or fewer vertices.

  • From the N vertices, choose one uniformly at random that belongs to a connected component with K+1 or more vertices. Delete all edges with the chosen vertex as an endpoint.

Find the expected value of the number of times the operation is performed, modulo 998244353.

How to print an expected value modulo \text{mod }{998244353}

It can be proved that the sought expected value is always a rational number. Additionally, under the constraints of this problem, it can also be proved that when that value is represented as an irreducible fraction \frac{P}{Q}, we have Q \not \equiv 0 \pmod{998244353}. Thus, there is a unique integer R such that R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353. Report this R.

Constraints

  • 1 \leq K < N \leq 100
  • 1 \leq A_i,B_i \leq N
  • The given graph is a tree.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N K
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}

Output

Print the answer.

Sample Input 1

4 2
1 2
2 3
2 4

Sample Output 1

249561090

For example, if the first operation chooses vertex 2, it deletes all edges, after which each connected component has not more than two vertices, so we finish performing the operation. On the other hand, if the first operation chooses vertex 1, there will still be a connected component with vertices 2, 3, and 4, so we perform the second operation.

The expected value of the number of operations is \frac{7}{4}.

Sample Input 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

Sample Output 2

181196154