問題一覧 > 通常問題

No.1507 Road Blocked

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 147
作問者 : 遭難者遭難者 / テスター : oliverx3oliverx3 magstamagsta yuto1115yuto1115
2 ProblemId : 6260 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-05-14 19:19:04

問題文

$N$ 頂点からなる木 $G$ が与えられます。各頂点にそれぞれ $1$ 以上 $N$ 以下の番号が割り振られており、 $i$ 番目の辺は頂点 $u_i$ と頂点 $v_i$ を繋いでいます。

$G$ から完全ランダムに $2$ つの異なる頂点 $A,B$ と $1$ つの辺 $E$ を選びます。

$G$ から $E$ を除いた時に $A$ と $B$ が連結である確率を求めてください。

ただし、この確率は有理数であることが証明できるので、注記で述べるように $\text{mod}\ 998244353$ で求めてください。

注記

有理数を出力する際は、まずその有理数を分数 $\displaystyle\frac pq$ で表してください。ここで、 $p,q$ は整数であり、 $q$ は $998244353$ で割り切れてはなりません (この問題の制約下で、そのような表現は必ず可能です) 。そして、 $qk\equiv p\ \left(\text{mod}\ 998244353\right)$ を満たすような $0$ 以上 $998244353$ 未満の唯一の整数 $k$ を出力してください。

制約

  • 入力は全て整数である
  • $2\le N\le10^5$
  • $1\le u_i,v_i\le N$
  • 与えられるグラフは木である

    • 入力

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

    出力

    条件を満たす $k$ を出力せよ。

    サンプル

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

    求める確率は $\displaystyle\frac49$ です。 $\displaystyle 4\equiv 9k\ \text{mod}\ 998244353$ を満たす $998244353$ 未満の正整数は $776412275$ なので、これを出力してください。

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

    どう $A,B,E$ が選ばれても $A$ と $B$ は連結になりません。従って、 $0$ を出力してください。

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

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