AdditionalFile5577.zip

#5577. 「RMI 2025」Oranges

标签: 传统 | 时间限制: 750 ms | 内存限制: 512 MiB |

注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）

请在提交源代码前添加 #include "oranges.h"。

题目描述

题目译自 Romanian Master of Informatics 2025 Day2 T3 「Oranges」

在日本某处的动物园里，饲养员决定和水豚玩以下游戏：

水豚的围栏由 $N$ 个温泉组成，编号从 $0$ 到 $N-1$。这些温泉由 $N-1$ 条步道连接。每条步道连接两个温泉，并且通过这些步道可以从任意一个温泉到达任何其他温泉。换句话说，水豚围栏具有树的结构（即无向连通无环图）。

最初，每个温泉中最多有一只水豚，但这在游戏过程中可能会改变。

游戏包含若干轮（可能是无限轮）。每一轮有 $2$ 个阶段：

1. 饲养员将一个橘子扔进 $N$ 个温泉中的一个。水豚会知道橘子被扔进了哪个温泉。
2. 最多有一只水豚可以移动到相邻的温泉。之后，如果包含橘子的温泉中没有水豚，则饲养员获胜，水豚失败。否则，橘子被吃掉，游戏继续。

如果饲养员和水豚都采取最优策略，且饲养员无法在有限轮次内赢得游戏，则称初始配置（即最初包含水豚的温泉集合）是安全的。

对于从 $0$ 到 $N$ 的每个 $K$，找出恰好有 $K$ 只水豚的安全初始配置的数量。由于这些数字可能很大，请找出它们对 $998244353$ 取模后的余数。

实现细节

你需要实现以下函数：

std::vector<int> solve(int N, std::vector<int> U, std::vector<int> V)

该函数由评测程序调用一次，并应返回一个长度为 $N+1$ 的 std::vector<int>，其中包含对于每个 $0 \leq K \leq N$，恰好有 $K$ 只水豚的安全初始配置的数量（对 $998244353$ 取模）。

此函数的参数含义如下：

• $N$：温泉的数量。
• $U$：一个长度为 $N-1$ 的 std::vector<int>，包含 $N-1$ 条步道的第一个端点。
• $V$：一个长度为 $N-1$ 的 std::vector<int>，包含 $N-1$ 条步道的第二个端点。

对于每个 $0 \leq i < N-1$，第 $i$ 条步道连接温泉 $U_{i}$ 和 $V_{i}$。

不要忘记包含头文件 oranges.h，否则你会得到编译错误！

样例 1

输入

1

输出

0 1

唯一安全的初始配置是 $\{0\}$。

样例 2

输入

4 
0 1
1 2
2 3

输出

0 0 4 4 1

第二个样例中水豚围栏的结构：

有 $4$ 种包含两只水豚的安全初始配置：$\{0,2\},\{0,3\},\{1,2\},\{1,3\}$。

所有至少有 $3$ 只水豚的初始配置都是安全的。

样例 3

输入

6
0 1
1 2
1 3
0 4
4 5

输出

0 0 0 0 11 6 1

第三个样例中水豚围栏的结构：

例如，初始配置 $\{1,3,4\}$ 是不安全的：

在第一轮，饲养员将橘子扔进温泉 $5$。来自温泉 $4$ 的水豚被迫移动到温泉 $5$。

在第二轮，饲养员将橘子扔进温泉 $2$。来自温泉 $1$ 的水豚被迫移动到温泉 $2$。

在第三轮，饲养员将橘子扔进温泉 $0$。由于没有水豚能移动到温泉 $0$，饲养员获胜

样例 4

输入

15 
0 1
0 2
2 3
3 4
4 5
5 6
0 7
7 8
8 9
9 10
8 11
11 12
7 13
7 14

输出

0 0 0 0 0 0 0 0 0 560 992 793 361 98 15 1

第四个样例中水豚围栏的结构：

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N \leq 6000$
• 对于每条步道 $(U_{i}, V_{i})$，满足 $0 \leq U_{i}, V_{i} < N, U_{i} \neq V_{i}$
• 保证给定的步道构成一棵树（即无向连通无环图）。

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$4$	存在一个与所有其他温泉直接相连的温泉。
$2$	$11$	每个温泉最多与两个其他温泉直接相连。
$3$	$14$	$N \leq 10$
$4$	$9$	$N \leq 20$
$5$	$33$	$N \leq 200$
$6$	$29$	无附加限制