問題一覧 > 通常問題

No.2504 NOT Path Painting

レベル : / AI推定難易度 : 2350 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 25
作問者 : suisen / テスター : emthrm torisasami4 rniya
お気に入りにしたユーザー ProblemId : 9243 / 自分の提出
問題文最終更新日: 2023-08-22 00:13:06
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 408 (順位表) の他の問題:

Problem Statement

You are given a tree with $n\ (n\geq 2)$ vertices numbered $1,2,\ldots,n$. The $i\ (1\leq i\leq n - 1)$-th edge connects vertex $u _ i$ and vertex $v _ i$.

Initially, all $n$ vertices are painted white. The following operation is repeated until all vertices are painted black.

  • Choose $1$ vertex pair $(x, y)$ satisfying $1\leq x \leq y\leq n$ uniformly at random. That is, each vertex pair is chosen with probability $\dfrac{1}{n(n+1)/2}$. For the chosen $(x, y)$, paint black all vertices that are not contained in the $xy$ simple path (including the endpoints $x, y$). Note that the $xy$ simple path is uniquely determined for a vertex pair $(x, y)$.

Assuming that the choices of vertex pairs are independent across operations, find the expected number of operations $\mathrm{mod}\ 998244353$.

You are given $T$ test cases; solve the above problem for all of them.

Definition of the expected value $\mathrm{mod}\ 998244353$ (click to expand)

It can be proved that, under the constraints of this problem, the expected value to be found is always a rational number, and that when this value is expressed as an irreducible fraction $\dfrac{P}{Q}$, we have $Q\not\equiv 0 \pmod{998244353}$. Therefore, there is a unique integer $R$ satisfying $R\times Q=P\pmod{998244353},0\leq R\lt 998244353$. Output this $R$.

Input

The input is given from standard input in the following format.

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

Here, $\text{testcase}_i$ denotes the $i$-th test case. The $i$-th test case is given in the following format.

$n$
$u _ 1\ v _ 1$
$u _ 2\ v _ 2$
$\vdots$
$u _ {n - 1}\ v _ {n - 1}$
  • All input values are integers
  • $1\leq T\leq 10 ^ 5$
  • $2\leq n\leq 4\times 10 ^ 4$
  • $1\leq u _ i, v _ i \leq n$
  • The given graph is a tree
  • The sum of $n$ over all test cases is at most $2\times 10 ^ 5$

Output

Output $T$ lines.

On line $i\ (1\leq i\leq T)$, output the answer to the $i$-th test case.

Output a newline after line $T$ as well.

Sample

Sample 1
Input
2
3
1 2
2 3
7
1 2
1 3
2 4
2 5
3 6
3 7
Output
4
559621838
  • For test case 1:

    The input represents the following tree.

    One possible sequence of operations is as follows.

    • Operation $1$: Choose $(x,y)=(1,3)$. The vertices on the $xy$ simple path are $\lbrace 1, 2, 3 \rbrace$, so no vertex is newly painted black.
    • Operation $2$: Choose $(x,y)=(1,2)$. The vertices on the $xy$ simple path are $\lbrace 1, 2 \rbrace$, so vertex $3$ is newly painted black.
    • Operation $3$: Choose $(x,y)=(1,2)$. The vertices on the $xy$ simple path are $\lbrace 1, 2 \rbrace$, so no vertex is newly painted black (vertex $3$, which is not contained in the path, is already painted black).
    • Operation $4$: Choose $(x,y)=(2,3)$. The vertices on the $xy$ simple path are $\lbrace 2, 3 \rbrace$, so vertex $1$ is newly painted black.
    • Operation $5$: Choose $(x,y)=(1,1)$. The vertices on the $xy$ simple path are $\lbrace 1 \rbrace$, so vertex $2$ is newly painted black. All vertices are now painted black, so the process ends here. The number of operations until the end is $5$.

    Another possible sequence of operations is the following.

    • Operation $1$: Choose $(x,y)=(1,1)$. The vertices on the $xy$ simple path are $\lbrace 1\rbrace$, so vertices $2, 3$ are newly painted black.
    • Operation $2$: Choose $(x,y)=(2,3)$. The vertices on the $xy$ simple path are $\lbrace 2, 3 \rbrace$, so vertex $1$ is newly painted black. All vertices are now painted black, so the process ends here. The number of operations until the end is $2$.

    It can be proved that, for this input, the expected number of operations until the end is $4$.

  • For test case 2:

    The expected value is $\dfrac{247}{66}$. Therefore, output $559621838$, the unique integer satisfying $66 \times R\equiv 247 \pmod{998244353}$ and $0\leq R\lt 998244353$.

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