問題一覧 > 通常問題

No.2504 NOT Path Painting

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 24
作問者 : suisensuisen / テスター : 👑 emthrmemthrm torisasami4torisasami4 rniyarniya
2 ProblemId : 9243 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-08-22 00:13:06

問題文

頂点に $1,2,\ldots,n$ の番号が付いた、$n\ (n\geq 2)$ 頂点の木が与えられます。$i\ (1\leq i\leq n - 1)$ 番目の辺は頂点 $u _ i$ と頂点 $v _ i$ を結んでいます。

はじめ、$n$ 個の頂点は全て白く塗られています。以下の操作を頂点が全て黒く塗られるまで行います。

  • $1\leq x \leq y\leq n$ を満たす頂点対 $(x, y)$ を一様ランダムに $1$ つ選択する。つまり、各頂点対はそれぞれ確率 $\dfrac{1}{n(n+1)/2}$ で選択される。選択した $(x, y)$ に対して、$xy$ 単純パス (端点 $x, y$ を含む) に 含まれない 頂点を全て黒く塗る。頂点対 $(x, y)$ に対して $xy$ 単純パスは一意に定まることに注意してください。

頂点対の選択は操作毎に独立であると仮定した場合の操作回数の期待値を $\mathrm{mod}\ 998244353$ で求めてください。

$T$ 個のテストケースが与えられるので、その全てに対して上記の問題を解いてください。

期待値 $\mathrm{mod}\ 998244353$ の定義 (クリックで展開)

本問題の制約下において、求める期待値は必ず有理数になること、およびその値を既約分数 $\dfrac{P}{Q}$ で表したときに $Q\not\equiv 0 \pmod{998244353}$ となることを証明できます。よって、$R\times Q=P\pmod{998244353},0\leq R\lt 998244353$ を満たす整数 $R$ が一意に定まります。この $R$ を答えてください。

入力

入力は以下の形式で標準入力から与えられます。

$T$
$\text{testcase}_1$
$\text{testcase}_2$
$\vdots$
$\text{testcase}_T$

ここで、$\text{testcase}_i$ は $i$ 番目のテストケースを表します。$i$ 番目のテストケースは、以下の形式で与えられます。

$n$
$u _ 1\ v _ 1$
$u _ 2\ v _ 2$
$\vdots$
$u _ {n - 1}\ v _ {n - 1}$
  • 入力は全て整数で与えられる
  • $1\leq T\leq 10 ^ 5$
  • $2\leq n\leq 4\times 10 ^ 4$
  • $1\leq u _ i, v _ i \leq n$
  • 与えられるグラフは木である
  • 全てのテストケースにわたる $n$ の総和は $2\times 10 ^ 5$ 以下である

出力

$T$ 行出力してください。

$i\ (1\leq i\leq T)$ 行目には、$i$ 個目のテストケースに対する答えを出力してください。

$T$ 行目の出力の後も改行してください。

サンプル

サンプル1
入力
2
3
1 2
2 3
7
1 2
1 3
2 4
2 5
3 6
3 7
出力
4
559621838

  • 1 つ目のテストケースについて:

    入力は次の木を表しています。

    操作の一例としては、例えば次のようなものが考えられます。

    • $1$ 回目: $(x,y)=(1,3)$ を選択する。$xy$ 単純パス上の頂点は $\lbrace 1, 2, 3 \rbrace$ であるから、新たに黒く塗られる頂点は存在しない。
    • $2$ 回目: $(x,y)=(1,2)$ を選択する。$xy$ 単純パス上の頂点は $\lbrace 1, 2 \rbrace$ であるから、新たに頂点 $3$ が黒く塗られる。
    • $3$ 回目: $(x,y)=(1,2)$ を選択する。$xy$ 単純パス上の頂点は $\lbrace 1, 2 \rbrace$ であるから、新たに黒く塗られる頂点は存在しない (パスに含まれない頂点 $3$ は既に黒く塗られている)。
    • $4$ 回目: $(x,y)=(2,3)$ を選択する。$xy$ 単純パス上の頂点は $\lbrace 2, 3 \rbrace$ であるから、新たに頂点 $1$ が黒く塗られる。
    • $5$ 回目: $(x,y)=(1,1)$ を選択する。$xy$ 単純パス上の頂点は $\lbrace 1 \rbrace$ であるから、新たに頂点 $2$ が黒く塗られる。全ての頂点が黒く塗られたので、ここで操作を終了する。終了するまでの操作回数は $5$ である。

    操作の例として、次のようなものも考えられます。

    • $1$ 回目: $(x,y)=(1,1)$ を選択する。$xy$ 単純パス上の頂点は $\lbrace 1\rbrace$ であるから、新たに頂点 $2, 3$ が黒く塗られる。
    • $2$ 回目: $(x,y)=(2,3)$ を選択する。$xy$ 単純パス上の頂点は $\lbrace 2, 3 \rbrace$ であるから、新たに頂点 $1$ が黒く塗られる。全ての頂点が黒く塗られたので、ここで操作を終了する。終了するまでの操作回数は $2$ である。

    この入力に対して、終了するまでの操作回数の期待値は $4$ であることを証明できます。

  • 2 つ目のテストケースについて:

    期待値は $\dfrac{247}{66}$ です。従って、$66 \times R\equiv 247 \pmod{998244353}$ かつ $0\leq R\lt 998244353$ を満たす唯一の整数 $559621838$ を出力してください。

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