No.1784 Not a star yet...
タグ : / 解いたユーザー数 12
作問者 :
PCTprobability
/ テスター :
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もしくは右上の雲マークをクリックしてアカウントを作成してください。