問題一覧 > 通常問題

No.1784 Not a star yet...

レベル : / AI推定難易度 : 3225 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 12
作問者 : PCTprobability / テスター : NyaanNyaan
お気に入りにしたユーザー ProblemId : 7312 / 自分の提出
問題文最終更新日: 2021-12-13 00:09:56
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2021 (順位表) の他の問題:

Problem Statement

You are given an undirected graph with $N$ vertices and $N-1$ edges. The given graph has no multiple edges or self-loops, but it is not necessarily connected.

The $i$-th edge has length $l_i$ and initially connects $a_i$ and $b_i$.

Repeat the following operation until the graph becomes a star graph, that is, the complete bipartite graph $K_{1,N-1}$.

  • Choose $1$ edge at random. The probability of each edge being chosen is proportional to its length.
  • Delete the chosen edge.
  • There are $\frac{N(N-1)}{2}-(N-2)$ pairs of vertices with no edge between them; choose $1$ of them uniformly at random and connect the pair with an edge. The length of the added edge is the length of the deleted edge.

Find the expected number of operations $\bmod 998244353$. It has been confirmed that, under the constraints, the answer is a rational number representable $\bmod 998244353$.

Constraints

  • All inputs are integers.
  • $2 \le N \le 250$
  • $1 \le a_i,b_i \le N$
  • The given graph has no multiple edges or self-loops.
  • $1 \le l_i \le 2$

Input

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

Output

Output the answer on $1$ line.

Sample

Sample 1
Input
4
1 2 1
2 3 1
1 3 2
Output
5

For example, the probability that the operations proceed from the left to the middle and then to the right as shown below is $\displaystyle \frac{2}{4} \times \frac{1}{4} \times \frac{1}{4} \times \frac{1}{4} = \frac{1}{128}$, and the number of operations is $2$.

It can also be proved that the answer is $5$.

Sample 2
Input
3
1 2 1
1 3 2
Output
0

Since the graph is a star graph from the beginning, the expected number of operations is $0$.

Sample 3
Input
7
1 2 2
2 4 1
3 5 1
4 7 2
1 7 2
3 6 2
Output
602774886

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