D - Tree Walking
Ceylon
2
s
1024
MB
450
点
問題文
$N$ 頂点の木があり、 $i$ 番目の辺は頂点 $u_i,v_i$ を結び、その長さは $d_i$ です。
umg くんはこの木の上を散歩することにしました。
umg くんは $1$ から $N$ の値からなる順列を選び、それを $P_1,P_2, \cdots, P_N$ とします。そして、頂点 $P_1$ に降り立ってから $i=1,2,\cdots, N-1$ について順に頂点 $P_i$ から頂点 $P_{i+1}$ に最短距離で移動することを繰り返し、頂点 $P_N$ にたどりついた時点で散歩を終了します。
長さ $N$ の順列は $N!$ 通りありますが、それぞれについて umg くんの移動距離を求め、その総和を $998244353$ で割った余りを出力してください。
制約
- $2 \leq N \leq 2 \times 10^5$
- $1 \leq u_i < v_i \leq N$
- $1 \leq d_i \leq 10^9$
- 与えられるグラフは木である。
- 入力される値はすべて整数である。
部分点
この問題には部分点が設定されています。
- $N \leq 8$ を満たすデータセットに正解した場合、100点が与えられます。
入力
入力は以下の形式で標準入力から与えられます。
$N$
$u_1$ $v_1$ $d_1$
$u_2$ $v_2$ $d_2$
$\vdots$
$u_{N-1}$ $v_{N-1}$ $d_{N-1}$
出力
答えを一行で出力してください。
入力例 1
3
1 2 2
2 3 5
出力例 1
56
頂点 $1,2,3$ を訪れる順列は、次の $6$ 通りです。
- $P=(1,2,3)$:移動距離は $2+5=7$
- $P=(1,3,2)$:移動距離は $7+5=12$
- $P=(2,1,3)$:移動距離は $2+7=9$
- $P=(2,3,1)$:移動距離は $5+7=12$
- $P=(3,1,2)$:移動距離は $7+2=9$
- $P=(3,2,1)$:移動距離は $5+2=7$
したがって、移動距離の総和は $7+12+9+12+9+7 = 56$ となります。
入力例 2
5
1 2 3
2 3 7
2 4 2
4 5 10
出力例 2
4416
入力例 3
8
1 2 4
1 3 8
2 4 1
2 5 100
3 6 6
6 7 3
6 8 50
出力例 3
13668480