分数: 1400 点
问题陈述
有一棵树 N 顶点编号自 1 to N,其中 i第一条边连接顶点 A_i 和 B_i.
我们现在将在之间随机写入实数 -(N-1) 和 1 (包含)在此树的每个顶点上。 随机数分布都是独立的均匀分布。
然后, 分数 树的 定义如下:
- 对于每个顶点 i,定义 x_i 如下:
- 包含顶点的连通子图的顶点上写入的值之和的最大值 i
- 如果存在 i 不满足 0 \leq x_i \leq 1,树的得分是 0.
- 否则,树的得分为 \prod_{1 \leq i \leq N} x_i.
求期望值 \text{mod }{998244353} 树的得分。
期望值的定义 \text{mod }{998244353}
可以证明,求的期望值始终是有理数。并且,在该问题的约束下,可以证明当该值表示为不可约分数时 \frac{P}{Q},我们有 Q \neq 0 \pmod{998244353}。因此,一个整数 R 满意 R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353 是唯一确定的。回答这个 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.