E - Tree Growing 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 900 点

問題文

頂点に 1 から N までの番号がついた N 頂点の木が与えられます。ここで N は 2 以上です。i 番目 (1\le i\le N-1) の辺は頂点 u_i と頂点 v_i を相互に結んでいます。

この木に対して操作をちょうど K 回行います。k 回目 (1\le k\le K) の操作は以下の通りです。

  • その時点での木の辺 N-2+k 本の中から、一本の辺を一様ランダムに選ぶ。選んだ辺が結ぶ頂点を u,v として、新たに頂点 N+k を用意し、頂点 u,N+k を結ぶ辺、頂点 v,N+k を結ぶ辺を追加する。その後、選んだ辺を削除する。

k=1,2,\ldots,K に対し、k 回目の操作後に、与えられた木は N+k 頂点の木になっていることに注意してください。

K 回の操作後の \displaystyle \sum_{1\le i < j\le N+K} \text{dist}(i,j) の期待値を \text{mod}\ 998244353 で求めてください。ただし、\text{dist}(i,j) で木の頂点 i と頂点 j の距離を表します。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

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

求める期待値は必ず有理数になることが証明できます。 また、この問題の制約のもとでは、求める有理数を既約分数 \displaystyle \frac{P}{Q} で表した時、Q \neq 0 \bmod 998244353 となることが証明できます。 よって、R \times Q \equiv P \bmod 998244353, 0 \leq R \lt 998244353 を満たす整数 R が一意に定まります。 この R を答えてください。

制約

  • 1\le T
  • 2\le N
  • 全てのテストケースにおける N の総和は 3\times 10^5 以下
  • 1\le K
  • 全てのテストケースにおける K の総和は 10^6 以下
  • 1\le u_i < v_i \le N
  • 与えられるグラフは木
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

各テストケースは以下の形式で与えられる。

N K
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}

出力

各テストケースに対する答えを順に改行区切りで出力せよ。

入力例 1

3
4 2
1 2
1 3
1 4
4 5
1 2
2 3
3 4
6 13
1 2
1 3
2 4
2 5
3 6

出力例 1

499122208
120
713032723

1 番目のテストケースについて考えます。

例えば 2 回の操作は以下のように進行します。

  • 1 回目：頂点 1 と頂点 2 を結ぶ辺が選ばれる。頂点 1 と頂点 5 を結ぶ辺、頂点 2 と頂点 5 を結ぶ辺が追加された後、頂点 1 と頂点 2 を結ぶ辺が削除される。
  • 2 回目：頂点 2 と頂点 5 を結ぶ辺が選ばれる。頂点 2 と頂点 6 を結ぶ辺、頂点 5 と頂点 6 を結ぶ辺が追加された後、頂点 2 と頂点 5 を結ぶ辺が削除される。

この場合の \displaystyle \sum_{1\le i < j\le N+K} \text{dist}(i,j) の値は 32 です。

\displaystyle \sum_{1\le i < j\le N+K} \text{dist}(i,j) の値は \displaystyle \frac12 の確率で 31 に、\displaystyle \frac12 の確率で 32 になります。

Score : 900 points

Problem Statement

You are given a tree with N vertices numbered 1 to N. Here, N is at least 2. The i-th edge (1\le i\le N-1) connects vertices u_i and v_i.

Perform the following operation on this tree exactly K times. The k-th operation (1\le k\le K) is as follows.

  • Choose one of the N-2+k edges of the tree at that point uniformly at random. Let u and v be the vertices connected by the chosen edge. Prepare a new vertex N+k, add edges connecting vertices u and N+k and connecting vertices v and N+k, then delete the chosen edge.

Note that for k=1,2,\ldots,K, the tree will have N+k vertices after the k-th operation.

Find the expected value, modulo 998244353, of \displaystyle \sum_{1\le i < j\le N+K} \text{dist}(i,j) after K operations. Here, \text{dist}(i,j) denotes the distance between vertices i and j in the tree.

You are given T test cases; solve each of them.

Definition of expected value \ \text{mod}\ 998244353

It can be proved that the expected value to be found is always a rational number. Moreover, under the constraints of this problem, when this rational number is expressed as an irreducible fraction \displaystyle \frac{P}{Q}, it can be proved that Q \neq 0 \bmod 998244353. Thus, there is a unique integer R satisfying R \times Q \equiv P \bmod 998244353, 0 \leq R \lt 998244353. Find this R.

Constraints

  • 1\le T
  • 2\le N
  • The sum of N over all test cases is at most 3\times 10^5.
  • 1\le K
  • The sum of K over all test cases is at most 10^6.
  • 1\le u_i < v_i \le N
  • The given graph is a tree.
  • All input values are integers.

Input

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

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

Each test case is given in the following format:

N K
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}

Output

Output the answers for the test cases in order, separated by newlines.

Sample Input 1

3
4 2
1 2
1 3
1 4
4 5
1 2
2 3
3 4
6 13
1 2
1 3
2 4
2 5
3 6

Sample Output 1

499122208
120
713032723

Consider the first test case.

For example, the two operations proceed as follows.

  • Operation 1: The edge connecting vertices 1 and 2 is chosen. After adding edges connecting vertices 1 and 5 and connecting vertices 2 and 5, the edge connecting vertices 1 and 2 is deleted.
  • Operation 2: The edge connecting vertices 2 and 5 is chosen. After adding edges connecting vertices 2 and 6 and connecting vertices 5 and 6, the edge connecting vertices 2 and 5 is deleted.

In this case, the value of \displaystyle \sum_{1\le i < j\le N+K} \text{dist}(i,j) is 32.

The value of \displaystyle \sum_{1\le i < j\le N+K} \text{dist}(i,j) is 31 with probability \displaystyle \frac12 and 32 with probability \displaystyle \frac12.