ゆるふわ競技プログラミングオンサイト at FORCIA #9
コンテスト日時
2026/11/07 (Sa) 14:15 - 16:45

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
提出
C++23 (g++ 12.2.0)