给定n和k，求满足特定约束的根树的最大节点数

问题核心分析 #

要最大化这类根树的节点数，本质是统计所有满足条件的k元正整数有序序列的总数——因为规则禁止重复节点，所以最多能包含所有符合要求的序列，且必然能将这些序列组织成满足父节点和<子节点和的树结构（构造逻辑见下文）。

最大节点数计算 #

每个节点是k个正整数的有序序列，设其和为s：

• s的有效取值范围是 k ≤ s ≤ n（k个正整数的最小和为k，每个数至少为1；若n < k，则不存在符合条件的节点，结果为0）。
• 对于固定的s，k个正整数有序序列和为s的数量可通过隔板法推导：令每个数x_i = y_i + 1（y_i ≥ 0），则转化为求y_1 + y_2 + ... + y_k = s - k的非负整数解数量，结果为组合数 C(s-1, k-1)。

所有符合条件的序列总数，是从s=k到s=n的C(s-1, k-1)之和。根据组合数累加性质：

C(k-1, k-1) + C(k, k-1) + ... + C(n-1, k-1) = C(n, k)

因此，最大节点数为组合数C(n, k)（当n ≥ k时；n < k时为0）。

树的构造验证 #

要将所有序列组织成符合规则的根树，只需按以下方式操作：

1. 按序列和从小到大分层，每层s对应所有和为s的k元有序序列。
2. 选择任意一个和为k的序列作为根节点（例如全1序列(1,1,...,1)）。
3. 对于任意层s的节点，将其挂载到任意层s' < s的节点下作为子节点（只需保证父节点和小于子节点和即可）。
   这种结构天然满足所有给定规则，且包含了所有可能的节点。

数据结构辅助 #

若需要实际构造这棵树，可使用分层数组/哈希表：

• 外层用数组索引表示序列和s，每个索引对应一个列表，存储所有和为s的k元有序序列。
• 构造树时，从根层开始，依次将下层节点挂载到任意上层节点即可，无需复杂结构。

内容的提问来源于stack exchange，提问作者CheongJu Not Apple