标签：子树 ARC162D Vertices 好树 Smallest 顶点

[ARC162D] Smallest Vertices

Atcoder：[ARC162D] Smallest Vertices

洛谷：[ARC162D] Smallest Vertices

Problem

在本问题中，当我们提到有根有向树时，我们指的是所有边都指向从根到叶子的有根树。

给定一个使得其总和为 \(N-1\) 的非负整数序列 \(d=(d_1,d_2,\ldots,d_N)\)。

对于带编号从 \(1\) 到 \(N\) 的顶点，假设 \(1\) 是根，我们将其点度数定义为 \(d_i\)。

我们称满足以下条件的根付有向树为好树：

• 点 \(i\) 的出度是 \(d_i\)。

此外，对于好树的顶点 \(v\)，定义 \(f(v)\) 为“包含顶点 \(v\) 的子树中的顶点（包括 \(v\)）的顶点编号的最小值”。我们将满足 \(f(v)=v\) 的顶点称为好顶点。

求好树中所有好顶点的总数，将其对 \(998244353\) 取模后的余数。

• $ 2\ \leq\ N\ \leq\ 500 $
• $ 0\ \leq\ d_i\ \leq\ N-1 $
• $ d_1\ \geq\ 1 $
• $ \sum_{i=1}^N\ d_i\ =\ N-1 $

Solution

注意题目给的是出度不是度数。

则若只是问好树的数量，由 Prufer 序列可得知答案为 \(\frac{(n - 2)!d_1}{\prod\limits_{i = 1}^{n}d_i!}\)。这里乘 \(d_1\) 是因为 \(1\) 的度数就为出度。之后的这种形式同理。

现在询问这些好树中好顶点的数量，观察数据规模较小，不妨考虑枚举顶点，看有多少好树满足该点为好顶点。

设当前枚举的点为 \(u\)，则 \(u\) 的子树节点编号均在 \([u, n]\) 间。

先填 \(u\) 子树：选择点集 \(S(u \in S)\)，\(u\) 子树的方案数为：

\[\frac{(|S| - 2)!d_u}{\sum\limits_{i \in S}d_i!} \]

再将 \(u\) 子树作为整体与其它点形成完整的好树：

\[\frac{(n - |S| - 1)!d_1}{\sum\limits_{i \not\in S}d_i!} \]

这两个乘起来分母是定值，于是只需要确定 \(|S|\) 而非枚举 \(S\)，同时做一个 dp 求出 \(|S|\) 对应的 \(S\) 的数量。

计 \(f_{i, j, k}\) 表示考虑选取编号 \(\ge i\) 的点，共选 \(j\) 个点，这些点的 \(d\) 值之和为 \(k\) 的方案数。讨论是否选 \(i\)：

\[f_{i, j, k} = f_{i + 1, j, k} + f_{i + 1, j - 1, k - d_i} \]

考虑 \(S\) 中必选 \(u\)，\(|S| = j + 1\) 的 \(S\) 共有 \(f_{u + 1, j, j - d_{u}}\) 个。将其乘上之前那两坨式子贡献进答案：

\[\frac{(j - 1)!(n - j - 2)!d_1d_u}{\sum\limits_{i = 1}^{n}d_i!}f_{u + 1, j, j - d_u} \]

注意 \(u = 1\) 时，\(|S|\) 只能为 \(n\)。其实 \(u = 1\) 时的贡献就是好树的个数。

注意 \(d_u = 0\) 时，\(|S|\) 只能为 \(1\)。该情况的贡献也是好树的个数。

实现时可以把 \(f\) 的第一维滚掉，但是我懒。

code [ARC162D]

标签：子树,ARC162D,Vertices,好树,Smallest,顶点
From： https://www.cnblogs.com/Schucking-Sattin/p/17557581.html