注意事项

请完善这个代码

#include <iostream>
#include <vector>

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

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);

	int N; std::cin >> N;
	std::vector<int> U(N - 1);
	std::vector<int> V(N - 1);

	for (size_t i = 0; i < U.size(); i++) {
		std::cin >> U[i] >> V[i];
	}

	std::vector<int> ans = solve(N, U, V);
	for (auto i : ans) {
		std::cout << i << " ";
	}
	std::cout << "\n";
}

题目描述

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

水豚的围栏由 $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}$。

1

0 1

4 
0 1
1 2
2 3

0 0 4 4 1

6
0 1
1 2
1 3
0 4
4 5

0 0 0 0 11 6 1

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}$
• 保证给定的步道构成一棵树（即无向连通无环图）。

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