/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 1400 点
問題文
1 から N までの番号がついた N 頂点からなる木があり，i 番目の辺は頂点 A_i と頂点 B_i を結んでいます．
今からこの木の各頂点に -(N-1) 以上 1 以下の実数をランダムに書き込みます． 乱数の分布はすべて独立な一様分布です．
その後，木のスコアを次のように定義します．
- 各頂点 i について，x_i を以下のように定義する．
- 頂点 i を含むような連結な部分グラフの頂点に書かれた値の総和の最大値
- 0 \leq x_i \leq 1 を満たさない i が存在する場合，木のスコアは 0 となる．
- そうでない場合，木のスコアは \prod_{1 \leq i \leq N} x_i となる．
木のスコアの期待値を \text{mod }{998244353} で求めてください．
期待値 \text{mod }{998244353} の定義
求める期待値は必ず有理数になることが証明できます。 また、この問題の制約のもとでは、その値を既約分数 \frac{P}{Q} で表した時、Q \neq 0 \pmod{998244353} となることも証明できます。 よって、R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353 を満たす整数 R が一意に定まります。 この R を答えてください。
制約
- 1 \leq N \leq 5000
- 1 \leq A_i,B_i \leq N
- 入力されるグラフは木である
入力
入力は以下の形式で標準入力から与えられる．
N
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}
出力
答えを出力せよ．
入力例 1
1
出力例 1
499122177
スコアの期待値は 1/2 です．
入力例 2
2 1 2
出力例 2
873463809
スコアの期待値は 1/8 です．
入力例 3
3 1 2 2 3
出力例 3
842653798
スコアの期待値は 13/648 です．
入力例 4
5 1 2 2 3 3 4 4 5
出力例 4
132050425
スコアの期待値は 41/187500 です．
入力例 5
8 1 2 1 3 1 4 1 5 5 6 5 7 5 8
出力例 5
243711918
スコアの期待値は 2477/30064771072 です．
Score : 1400 points
Problem Statement
There is a tree with N vertices numbered from 1 to N, where the i-th edge connects vertices A_i and B_i.
We will now randomly write real numbers between -(N-1) and 1 (inclusive) on each vertex of this tree. The random number distributions are all independent uniform distributions.
Then, the score of the tree is defined as follows:
- For each vertex i, define x_i as follows:
- The maximum value of the sum of values written on vertices of connected subgraphs that contain vertex i
- If there exists i that does not satisfy 0 \leq x_i \leq 1, the tree's score is 0.
- Otherwise, the tree's score is \prod_{1 \leq i \leq N} x_i.
Find the expected value \text{mod }{998244353} of the tree's score.
Definition of expected value \text{mod }{998244353}
It can be proved that the sought expected value is always a rational number. Also, under the constraints of this problem, it can be proved that when the value is expressed as an irreducible fraction \frac{P}{Q}, we have Q \neq 0 \pmod{998244353}. Therefore, an integer R satisfying R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353 is uniquely determined. Answer this R.
Constraints
- 1 \leq N \leq 5000
- 1 \leq A_i, B_i \leq N
- The input graph is a tree.
Input
The input is given from Standard Input in the following format:
N
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}
Output
Output the answer.
Sample Input 1
1
Sample Output 1
499122177
The expected value of the score is 1/2.
Sample Input 2
2 1 2
Sample Output 2
873463809
The expected value of the score is 1/8.
Sample Input 3
3 1 2 2 3
Sample Output 3
842653798
The expected value of the score is 13/648.
Sample Input 4
5 1 2 2 3 3 4 4 5
Sample Output 4
132050425
The expected value of the score is 41/187500.
Sample Input 5
8 1 2 1 3 1 4 1 5 5 6 5 7 5 8
Sample Output 5
243711918
The expected value of the score is 2477/30064771072.