配点 : 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 获取点后,图形将发生如下图所示的变化。
入力例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 的余数。