请大家报名 UOJ Round #29！！！

为了防止被管理员隐藏，我来推一个题：【MX-X8-T4】「TAOI-3」Warmth of the Eternity。

题意简述：对于一棵 $n$ 个结点的有标号无根树，给出它每个点 $i$ 的度数 $d_i$ 以及删除该点后得到的 $d_i$ 个连通块的大小，问满足条件的原树有多少棵。答案对 $998244353$ 取模。保证至少存在一棵树满足条件，即取模前的答案非零。

数据范围：$2 \le n \le 3 \times 10^5$。

大家可以不用刷回复了，来想想这题咋做。

2025-02-09 更新：下面是该题出题人 251Sec 给出的做法。

删除某点后得到的连通块大小，其实就是以该点为根时的各孩子方向的子树大小。

回顾树的重心的定义，可以发现有了这些信息，就可以唯一确定该树的重心（可能是一个点，也可能是通过一条边相连的两个点）。

我们以重心为根，将无根树转化为有根树，并希望通过这种方式可以对树的可能结构有一个更清晰的把握。

现在我们可以获知每个点的子树大小，以及它所有孩子方向的子树大小。

回 Gorenstein 的问题：什么是“每个点的子树大小”？
这里指以重心为根时的子树大小，即去掉最大的那侧连通块后剩下的点数（熟知重心的性质是重心所在的那侧是最大的子树）。

现在我们考虑一个点 $u$，假设它有一个孩子方向的子树大小为 $\mathit{siz}$，且存在另一个点 $v$，它自身的子树大小恰好也是 $\mathit{siz}$。考虑这个问题：是否总是能将 $v$ 接在 $u$ 的下方，形成一个合法方案？

答案是肯定的。因为考虑另一个合法方案，并假设在该方案中，$v$ 没有接在 $u$ 的下方。则该方案中必然有另一个点 $v'$ 接在 $u$ 的下方，且 $v'$ 自身的子树大小恰好也是 $\mathit{siz}$。考虑进行调整：互换 $v$ 与 $v'$ 的位置（包括它们的整个子树），则形成的新方案必然也合法。为什么呢？考虑 $u$ 的孩子的限制，去掉了一个 $v'$ 又加入了一个 $v$，而这两点的子树大小是相同的，所以不会破坏 $u$ 的孩子的限制的合法性。对于 $v$ 的父节点（记作 $u'$）也是同理，去掉了一个 $v$ 又加入了一个 $v'$，也不会破坏合法性。

故结论是：任意的 $(u, v)$ 配对都能导出合法方案，只需满足 $u$ 的一个孩子方向的子树大小恰好等于 $v$ 的子树大小。在这个配对完成后，$u$ 的那一孩子方向的子树就被占用了，不能在后续配对中使用。

下面考虑整体的方案数：

对一个大小 $\mathit{siz} = k$，假设有 $a$ 个结点拥有孩子方向的子树大小恰好为 $k$ 的限制，且它们的这样的孩子方向个数分别为 $c_1, \ldots, c_a$，然后又有 $b$ 个结点的自身的子树大小恰好为 $k$。
显然，应满足 $c_1 + \cdots + c_a = b$，因为完整的配对方案中，必须恰好一一匹配。
不同的结点以任意顺序与同一个结点配对（接在同一个结点下方），产生的方案是相同的，故不能重复计入这些方案。
可以发现，每个方案就相当于为 $b$ 个结点染上 $a$ 种颜色之一，且满足染第 $i$ 种颜色的点数恰好为 $c_i$。
不难看出这就是多重组合数的组合意义，即 $\dbinom{b}{c_1, \ldots, c_a}$。
不同的 $k$ 是互相独立的，用乘法原理乘在一起即可。

最终的答案为 $\displaystyle \prod_k \binom{b}{c_1, \ldots, c_a}$。

只需预处理组合数，就可在 $O(n)$ 的时空复杂度内解决该题。

同时感谢 Luke_li、myee 与 newfiles 参与该题的讨论！（不难发现 myee 给出的做法等价于忽略“定重心为根”后的步骤。）你们为所有从洛谷前来 UOJ 的新用户开了个好头！希望大家友善讨论，减少对新用户的攻击，并引导他们改掉坏习惯，向善参与交流讨论。

我衷心相信，在所有热爱 UOJ 的用户的共同努力下，UOJ 的博客区可以从以往的死气沉沉，真正变成一个“多元、开放与包容”的学术讨论社区。一起努力吧！