← 返回题目列表

AtCoder · agc073_c

C. 子树之和的最大值的乘积

中文机器翻译题面 查看原题

分数: 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.