← 返回题目列表

AtCoder · dwacon6th_final_c

C. 树缩小

中文机器翻译题面 查看原题

配点 : 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 Niwango得到的总分的期望值为 乘以 (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 的余数。