AT_agc073_c.[AGC073C] Product of Max of Sum of Subtree

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一棵包含 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$ ，第 $i$ 条边连接顶点 $A_i$ 和 $B_i$ 。

现在，我们将在这棵树的每个顶点上随机写一个介于 $-(N-1)$ 到 $1$ （包含端点）的实数。所有顶点上随机数的分布都是独立的均匀分布。

树的得分定义如下：

对于每个顶点 $i$ $i$ ，定义 $x_i$ $x_{i}$ 如下：
- $x_i$ 为所有包含顶点 $i$ 的连通子图顶点权值和的最大值。
如果存在某个 $i$ 使得 $0 \leq x_i \leq 1$ 不成立，则该树的得分为 $0$ 。
否则，树的得分为 $\prod_{1 \leq i \leq N} x_i$ 。

请计算该树得分的期望值 $\bmod 998244353$ 。

期望值 $\bmod 998244353$ 的定义：可以证明本题答案一定为有理数。并且，在本题约束下，若用最简分数 $\frac{P}{Q}$ 表示答案，则有 $Q \not\equiv 0 \pmod{998244353}$ 。因此唯一确定一个整数 $R$ 满足 $R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353$ 。请输出这个 $R$ 。

输入格式

输入以如下格式由标准输入给出：

$N$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_{N-1}$ $B_{N-1}$

输出格式

输出答案。

输入输出样例

输入#1
```
1
```
输出#1
```
499122177
```
输入#2
```
2
1 2
```
输出#2
```
873463809
```
输入#3
```
3
1 2
2 3
```
输出#3
```
842653798
```
输入#4
```
5
1 2
2 3
3 4
4 5
```
输出#4
```
132050425
```
输入#5
```
8
1 2
1 3
1 4
1 5
5 6
5 7
5 8
```
输出#5
```
243711918
```

说明/提示

样例解释 1

这个得分的期望为 $1/2$ 。

样例解释 2

这个得分的期望为 $1/8$ 。

样例解释 3

这个得分的期望为 $13/648$ 。

样例解释 4

这个得分的期望为 $41/187500$ 。

样例解释 5

这个得分的期望为 $2477/30064771072$ 。

数据范围

$1 \leq N \leq 5000$
$1 \leq A_i, B_i \leq N$
输入保证图为一棵树。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页