問題一覧 > 通常問題

No.1507 Road Blocked

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 154
作問者 : 👑 qand / テスター : oliverx3 magsta yuto1115
お気に入りにしたユーザー ProblemId : 6260 / 自分の提出
問題文最終更新日: 2021-05-14 19:19:04
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
yukicoder contest 295 (順位表) の他の問題:

Problem Statement

You are given a tree $G$ with $N$ vertices. The vertices are numbered with integers from $1$ to $N$, and the $i$-th edge connects vertices $u_i$ and $v_i$.

Choose $2$ distinct vertices $A,B$ and $1$ edge $E$ from $G$ uniformly at random.

Find the probability that $A$ and $B$ are connected when $E$ is removed from $G$.

It can be proved that this probability is a rational number, so find it $\text{mod}\ 998244353$ as described in the Notes.

Notes

To output a rational number, first represent it as a fraction $\displaystyle\frac pq$, where $p,q$ are integers and $q$ must not be divisible by $998244353$ (under the constraints of this problem, such a representation is always possible). Then, output the unique integer $k$ that is at least $0$ and less than $998244353$ such that $qk\equiv p\ \left(\text{mod}\ 998244353\right)$.

Constraints

  • All input values are integers.
  • $2\le N\le10^5$
  • $1\le u_i,v_i\le N$
  • The given graph is a tree.

    • Input

    $N$
$u_1\ v_1$
$\vdots$
$u_{N-1}\ v_{N-1}$

    Output

    Output the $k$ that satisfies the condition.

    Sample

    Sample 1
    Input
    4
1 2
2 3
3 4
    Output
    776412275

    The probability to find is $\displaystyle\frac49$. The positive integer less than $998244353$ that satisfies $\displaystyle 4\equiv 9k\ \text{mod}\ 998244353$ is $776412275$, so output this.

    Sample 2
    Input
    2
1 2
    Output
    0

    No matter how $A,B,E$ are chosen, $A$ and $B$ are never connected. Therefore, output $0$.

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

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