問題一覧 > 通常問題

No.1507 Road Blocked

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

問題文

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

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

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

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

注記

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

制約

  • 入力は全て整数である
  • 2≤N≤105
  • 1≤ui,vi≤N
  • 与えられるグラフは木である

    • 入力

    N
u1 v1
⋮
uN−1 vN−1

    出力

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

    サンプル

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

    求める確率は 49 です。 4≡9k 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もしくは右上の雲マークをクリックしてアカウントを作成してください。