P16554 [ICPC 2026 LAC] Holes and Tunnels
题目描述
“挖洞动物”（Path-Digging Animals，PDA）是一款深受程序员喜爱的双人合作新游戏。游戏在一个包含 $N$ 个洞和 $N-1$ 条双向隧道的棋盘上进行。这些隧道构成一棵无向树，即每对洞之间有且仅有一条简单路径。
PDA 中的一条**路线**是指**两个不同洞**之间的一条简单路径。由于隧道是双向的，路线的方向无关紧要：从洞 $U$ 到洞 $V$ 的（唯一）路线与从洞 $V$ 到洞 $U$ 的（唯一）路线是相同的路线。
玩家使用动物形状的棋子来玩 PDA。在游戏的每一轮中，每个玩家独立选择一条路线，让他们的动物沿该路线移动，并且双方获得的分数等于他们各自路线共同经过的隧道数量。
现在，Alicia 和 Bruno 正在智利的一个桌游聚会上玩 PDA，他们想分析自己的得分可能性。对于 $k$ 从 $1$ 到 $N-1$ 的每个整数，他们想知道有多少 **有序** 路线对 $(A, B)$，使得如果 Alicia 选择路线 $A$ 而 Bruno 选择路线 $B$，则他们恰好得到 $k$ 分。
输入格式
第一行包含一个整数 $N$（$2 \le N \le 2 \times 10^5$），表示洞的数量。每个洞由 $1$ 到 $N$ 之间的一个不同整数标识。
接下来 $N-1$ 行，每行包含两个整数 $U$ 和 $V$（$1 \le U, V \le N$，$U \neq V$），表示洞 $U$ 与洞 $V$ 之间有一条双向隧道。保证这些隧道构成一棵无向树。
输出格式
输出一行，包含 $N-1$ 个整数 $P_1, P_2, \dots, P_{N-1}$，其中 $P_k$ 表示满足“Alicia 选择路线 $A$ 且 Bruno 选择路线 $B$ 时恰好得 $k$ 分”的有序路线对 $(A, B)$ 的数量。由于这些数可能很大，请输出每个数除以 $998244353$ 的余数。
说明/提示
**样例 1 解释：**
Alicia 的路线 $A$ 有三种可能：洞 $1$ 与洞 $3$ 之间的路线（由这两个洞之间的单条隧道组成）、洞 $2$ 与洞 $3$ 之间的路线（也是单条隧道）、以及洞 $2$ 与洞 $1$ 之间的路线（包含两条隧道）。Bruno 的路线 $B$ 同样有三种可能。下表展示了每种组合下的得分。可以看出，有 $6$ 个有序路线对得 $1$ 分，有 $1$ 个有序路线对得 $2$ 分。取模运算不会改变这些结果。
:::align{center}
:::
翻译由 DeepSeek V4 Pro 完成