C - Tree Shrinking /

Time Limit: 5.252 sec / Memory Limit: 1024 MB

配点 : 1200

問題文

1, \ldots, N の番号がついた N 個の頂点からなる木が与えられます。 1, \ldots, N-1 の番号がついた N-1 本の辺があり、辺 i は頂点 a_i,b_i をつないでいます。

ニワンゴ君は操作を N-1 回行います。i 回目の操作は以下の手順からなります。

  • 木の辺を等確率で選ぶ(選ばれた辺を e, e の端点を u,v とする)
  • u の次数を x, v の次数を y として xy 点得る
  • e を取り除き、u,v1 つの頂点にまとめる(すなわち辺の縮約を行う)。

N-1 回の操作によって、ニワンゴ君が得た得点の総和の期待値に (N-1)! をかけた値(これは整数になることが示せます)を 998244353 で割ったあまりを求めてください。

制約

  • 2 \leq N \leq 10^{5}
  • 1 \leq a_i, b_i \leq N
  • 与えられるグラフは木

入力

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

N
a_1 b_1
\vdots
a_{N-1} b_{N-1}

出力

答えを出力せよ。


入力例1

6
1 4
1 2
1 3
4 5
4 6

出力例1

1640
  • 例えば 1 回目の操作で辺 1 が選ばれた場合、9 点を得てグラフは以下の図のように変化します
f5f78a71a75bc641ea14315dcd873900.png

入力例2

3
1 2
2 3

出力例2

6

入力例3

20
12 10
12 14
12 9
17 9
1 17
1 2
11 2
11 15
13 11
13 4
5 1
20 5
3 4
16 11
3 18
17 8
20 7
6 3
19 2

出力例3

253636877
  • 答えを 998244353 で割ったあまりを求めてください。