C - Tree Shrinking
解説
/
実行時間制限: 5.252 sec / メモリ制限: 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,v を 1 つの頂点にまとめる(すなわち辺の縮約を行う)。
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 点を得てグラフは以下の図のように変化します
入力例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 で割ったあまりを求めてください。