No.2504 NOT Path Painting
タグ : / 解いたユーザー数 25
作問者 :
emthrm
torisasami4
rniya
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もしくは右上の雲マークをクリックしてアカウントを作成してください。