問題一覧 > 通常問題

No.1784 Not a star yet...

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 5
作問者 : PCTprobabilityPCTprobability / テスター : NyaanNyaanNyaanNyaan
4 ProblemId : 7312 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-12-13 00:09:56

問題文

$N$ 頂点 $N-1$ 辺無向グラフが与えられます。与えられるグラフに多重辺、自己ループはありませんが、連結であるとは限りません。

$i$ 本目の辺は、長さ $l_i$ の辺で、始めは $a_i$ と $b_i$ をつないでいます。

グラフがスターグラフ、すなわち完全二部グラフ $K_{1,N-1}$ になるまで、以下の操作を繰り返します。

  • 辺をランダムに $1$ 本選びます。それぞれの辺が選ばれる確率は辺の長さに比例します。
  • 選んだ辺を消します。
  • 間に辺がないような頂点の組は $\frac{N(N-1)}{2}-(N-2)$ 個ありますが、等確率で $1$ 個を選び間を辺でつなぎます。追加する辺の長さは消した辺の長さとします。

操作回数の期待値 $\bmod 998244353$ を求めてください。制約上、解は $\bmod 998244353$ 上で表現可能な有理数であることが確認されています。

制約

  • 入力は全て整数である。
  • $2 \le N \le 250$
  • $1 \le a_i,b_i \le N$
  • 与えられるグラフに多重辺、自己ループは存在しない。
  • $1 \le l_i \le 2$

入力

$N$
$a_1\ b_1\ l_1$
$a_2\ b_2\ l_2$
$\vdots$
$a_{N-1}\ b_{N-1}\ l_{N-1}$

出力

答えを $1$ 行に出力してください。

サンプル

サンプル1
入力
4
1 2 1
2 3 1
1 3 2
出力
5

例えば、以下の左から真ん中、そして右のように操作が実行される確率は $\displaystyle \frac{2}{4} \times \frac{1}{4} \times \frac{1}{4} \times \frac{1}{4} = \frac{1}{128}$ であり操作回数は $2$ 回です。

また、解は $5$ であることが証明可能です。

サンプル2
入力
3
1 2 1
1 3 2
出力
0

初めからスターグラフであるため、操作回数の期待値は $0$ です。

サンプル3
入力
7
1 2 2
2 4 1
3 5 1
4 7 2
1 7 2
3 6 2
出力
602774886

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。