233的树 - 题解

标签与难度

标签: 组合数学, 计数问题, 树的性质, 树的直径, 费马小定理, 模块化算术难度: 1900

题目大意喵~

主人你好呀，喵~ 这道题是说，给我们一个整数 $n$ ，代表一棵树有 $n$ 个节点。

我们定义了一个函数 $f(d_1, d_2, \dots, d_n)$ ，它表示当一棵 $n$ 个节点的树，其各个节点的度数分别为 $d_1, d_2, \dots, d_n$ 时，这棵树的最大可能直径是多少。如果这个度数序列根本无法构成一棵树，那么 $f$ 函数的值就是 0。

这里的“树的直径”是指树上距离最远的两个点之间的距离。而“距离”被定义为这两点之间路径上的节点数（包括端点自己哦）。

我们的任务，就是要求出所有可能的、能构成树的、且每个点的度数 $d_i$ 都是正整数的度数序列 $(d_1, \dots, d_n)$ ，它们对应的 $f$ 函数值的总和。也就是计算 $\sum f(d_1, d_2, \dots, d_n)$ ，最后结果要对 $10^9+7$ 取模，喵~

举个栗子，如果 $n=3$ ，可能的度数序列只有 $(1, 2, 1)$ 。这构成了一条链，直径是 3。所以对于 $n=3$ ，答案就是 3。

解题思路分析

这道题看起来好复杂呀，要我们遍历所有可能的度数序列，呜...猫猫的脑袋要转不过来了！(>ω<) 但是别怕，我们静下心来，一步一步把问题拆解开，肯定能找到线索的，呐！

第一步：直径和树的结构有什么关系？

首先，我们要最大化树的直径。想让树的直径最大，最好的办法就是把树的结构变得“细长”，就像一根猫尾巴一样，而不是像一团毛球，对吧？最长的路径，也就是直径，它的两个端点一定是叶子节点（度数为 1 的点）。

如果我们一棵树有 $k$ 个叶子节点，那么它就有 $n-k$ 个非叶子节点（度数 $\ge 2$ ）。为了让直径最长，我们可以把这 $n-k$ 个非叶子节点排成一条长链，作为树的主干。然后把 $k$ 个叶子节点挂在这条主干上。

最长的路径，自然是从主干一端的一个叶子节点，走过整条主干，到达另一端的一个叶子节点。这条路径会经过 $2$ 个叶子节点和全部 $n-k$ 个非叶子节点。所以，路径上的节点总数就是 $(n-k) + 2$ 。

因此，对于一个给定的度数序列，如果它有 $k$ 个度数为 1 的节点（叶子节点），那么我们可以构造出的树的最大直径就是 $n-k+2$ 。

第二步：转变思路，不枚举度数序列！

直接枚举所有可能的度数序列太可怕了，数量太多啦！我们不如换个角度。既然最大直径只和叶子节点的数量 $k$ 有关，我们可以不可以直接枚举 $k$ 呢？

好像可以！但是，如果枚举叶子数量 $k$ ，我们就需要计算“有多少个合法的度数序列恰好有 $k$ 个叶子”，这依然有点绕。

那我们再换个角度！既然有叶子节点，那就有非叶子节点。我们来枚举非叶子节点的数量，设为 $i$ 。

一棵树（当 $n>2$ 时）至少有 2 个叶子节点，所以非叶子节点的数量 $i$ 最多是 $n-2$ 。
同时，只要有边，就至少有一个非叶子节点（除非 $n=2$ 的情况，两个点都是叶子）。所以 $i$ 至少是 1。
所以，非叶子节点的数量 $i$ 的取值范围是 $1 \le i \le n-2$ 。（对于 $n=2$ 的情况，我们最后单独处理就好啦~）

第三步：神奇的组合计数魔法！

好！现在我们固定了非叶子节点的数量为 $i$ 。接下来我们来解决三个小问题：

这棵树的最大直径是多少？ 如果非叶子节点有 $i$ 个，那么叶子节点就有 $k = n-i$ 个。根据我们第一步的分析，最大直径就是 $n-k+2 = n - (n-i) + 2 = i+2$ 。
有多少种方法确定哪些点是非叶子节点？ 这很简单！我们有 $n$ 个节点，要从中选出 $i$ 个作为非叶子节点。这就是一个组合问题，方法数是 $\binom{n}{i}$ 。
对于这 $i$ 个非叶子节点，有多少种分配度数的方法？ 这是最关键的一步，喵！我们要用到一点图论知识和“插板法”（也叫“星星和杠杠”）。
- 总度数和： 一棵 $n$ 个节点的树，有 $n-1$ 条边。根据握手定理，所有节点的度数之和为 $2 \times (\text{边数}) = 2(n-1)$ 。
- 非叶子节点度数和： 我们有 $n-i$ 个叶子节点，它们的度数都是 1，所以度数和是 $n-i$ 。那么剩下的 $i$ 个非叶子节点的度数之和就是 $2(n-1) - (n-i) = n+i-2$ 。
- 度数限制： 这 $i$ 个非叶子节点的度数都必须大于等于 2。
- 插板法登场！ 我们要找的是方程 $d'_1 + d'_2 + \dots + d'_i = n+i-2$ 的正整数解的个数，其中每个 $d'_j \ge 2$ 。为了使用标准的插板法，我们做一个小小的换元。令 $e_j = d'_j - 2$ ，那么 $e_j \ge 0$ 。原方程就变成了：
$(e_1+2) + (e_2+2) + \dots + (e_i+2) = n+i-2$
$(e_1 + e_2 + \dots + e_i) + 2i = n+i-2$
$e_1 + e_2 + \dots + e_i = n-i-2$
现在问题变成了：把 $n-i-2$ 个相同的小球（“星星”）放进 $i$ 个不同的盒子里（“变量”），允许盒子为空。这是一个经典的插板法问题！我们需要 $i-1$ 个隔板。总的方案数是 $\binom{(\text{星星数}) + (\text{隔板数})}{(\text{隔板数})} = \binom{(n-i-2) + (i-1)}{i-1} = \binom{n-3}{i-1}$ 。

第四步：汇总答案！

我们已经把所有零件都准备好啦！现在把它们组装起来！对于一个固定的非叶子节点数 $i$ （ $1 \le i \le n-2$ ）：

最大直径是 $(i+2)$ 。
选择非叶子节点的方法数是 $\binom{n}{i}$ 。
分配度数的方法数是 $\binom{n-3}{i-1}$ 。

根据乘法原理，当非叶子节点数为 $i$ 时，对总答案的贡献就是：

\text{贡献}_i = (i+2) \times \binom{n}{i} \times \binom{n-3}{i-1}

最后，我们把所有可能的 $i$ （从 1 到 $n-2$ ）的贡献加起来，就是最终的答案啦！

\text{总和} = \sum_{i=1}^{n-2} \left( (i+2) \times \binom{n}{i} \times \binom{n-3}{i-1} \right)

特殊情况：当 $n=2$ 时，两个点都是叶子，度数序列是 $(1,1)$ ，直径是 2。上面的公式在 $i$ 的循环范围是 $1$ 到 $0$ ，不会执行，所以需要特判一下。

现在，我们只需要预处理阶乘和阶乘的逆元，就可以快速计算组合数，然后循环求解了！冲呀，喵！

代码实现

这是我根据上面的思路，精心重构的一份代码，注释超详细的哦！希望能帮到你，喵~

cpp

#include <iostream>
#include <vector>

// 使用 long long 防止中间计算溢出
using int64 = long long;

// 模数
const int MOD = 1e9 + 7;

// 快速幂函数，用于计算 a^b % MOD
// 原理是二进制分解指数
int64 power(int64 base, int64 exp) {
    int64 res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) {
            res = (res * base) % MOD;
        }
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

// 费马小定理求逆元：a^(p-2) % p
int64 modInverse(int64 n) {
    return power(n, MOD - 2);
}

// 预计算阶乘和阶乘逆元的数组
std::vector<int64> fact;
std::vector<int64> invFact;

// 预处理阶乘和逆元
void precompute_factorials(int n) {
    fact.resize(n + 1);
    invFact.resize(n + 1);
    fact[0] = 1;
    invFact[0] = 1;
    for (int i = 1; i <= n; ++i) {
        fact[i] = (fact[i - 1] * i) % MOD;
        invFact[i] = modInverse(fact[i]); // 也可以递推求逆元，但单次求速度也足够
    }
}

// 组合数计算函数 C(n, k) = n! / (k! * (n-k)!)
int64 combinations(int n, int k) {
    if (k < 0 || k > n) {
        return 0; // 不合法的情况，方案数为0
    }
    // C(n, k) = fact[n] * invFact[k] * invFact[n-k]
    return (((fact[n] * invFact[k]) % MOD) * invFact[n - k]) % MOD;
}

int main() {
    // 加速输入输出，让猫猫跑得更快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    // 特殊情况：n=2 时，只有一种树（一条边），度数序列(1,1)，直径为2
    if (n == 2) {
        std::cout << 2 << std::endl;
        return 0;
    }

    // 预处理阶乘到 n
    precompute_factorials(n);

    int64 total_sum = 0;

    // 根据我们的公式进行求和
    // i 是非叶子节点的数量，范围从 1 到 n-2
    for (int i = 1; i <= n - 2; ++i) {
        // 直径是 i + 2
        int64 diameter = i + 2;
        
        // 选择 i 个非叶子节点的方法数
        int64 ways_to_choose_nodes = combinations(n, i);
        
        // 分配度数的方法数
        int64 ways_to_assign_degrees = combinations(n - 3, i - 1);
        
        // 当前 i 的贡献
        int64 contribution = (diameter * ways_to_choose_nodes) % MOD;
        contribution = (contribution * ways_to_assign_degrees) % MOD;
        
        // 累加到总和
        total_sum = (total_sum + contribution) % MOD;
    }

    std::cout << total_sum << std::endl;

    return 0;
}

复杂度分析

时间复杂度: $O(N + \log P)$
- 预处理阶乘需要 $O(N)$ 的时间。
- 在预处理中，我们为每个阶乘计算逆元，每次使用快速幂是 $O(\log P)$ ，总共是 $O(N \log P)$ 。不过，我们也可以用 $O(N)$ 的递推方式求所有逆元（inv[i] = (MOD - MOD/i) * inv[MOD%i] % MOD），或者求出 invFact[n] 后再 $O(N)$ 递推 invFact[i] = invFact[i+1] * (i+1) % MOD。在我的代码里为了简洁用了快速幂，但即使如此，对于 $N \le 10^6$ 也是足够快的。
- 主循环从 $1$ 到 $n-2$ ，执行了 $O(N)$ 次。循环体内部的组合数计算是 $O(1)$ 的，因为我们已经预处理好了。
- 所以总的时间复杂度主要由预处理决定，为 $O(N)$ （如果我们用更优的逆元预处理方法）或者 $O(N \log P)$ 。
空间复杂度: $O(N)$
- 我们需要两个数组 fact 和 invFact 来存储阶乘和阶乘的逆元，它们的大小都和 $N$ 相关，所以空间复杂度是 $O(N)$ 。

知识点总结

这道题真是一次有趣的冒险，喵！我们用到了好多有趣的工具呢：

树的基本性质: 比如握手定理（度数和为边数的两倍），以及叶子节点的概念。
树的直径: 理解如何构造一棵树使其直径最大化，关键是形成“链状”结构。
组合数学: 核心解法依赖于组合计数。我们用 $\binom{n}{k}$ 来解决“选择”问题。
插板法 (Stars and Bars): 这是解决“将N个无区别物品分给K个有区别的人”这类问题的强大模型。在这里我们用它来计算分配度数的方案数。
模块化算术: 在计算过程中，所有结果都要对一个大质数取模。这就需要我们掌握：
- 快速幂: 高效计算 $a^b \pmod{p}$ 。
- 费马小定理: 在模数 $p$ 是质数时，用 $a^{p-2} \pmod{p}$ 来求 $a$ 的乘法逆元。
- 预处理: 预先计算好阶乘和它们的逆元，可以让我们在 $O(1)$ 的时间内查询组合数，大大提高效率。

通过这道题，我们学会了如何将一个看似复杂、需要枚举无穷多情况的问题，通过转换视角和运用数学工具，变成一个简洁的求和公式。是不是很有成就感呀？继续加油哦，主人！喵~

233的树 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

第一步：直径和树的结构有什么关系？ ​

第二步：转变思路，不枚举度数序列！ ​

第三步：神奇的组合计数魔法！ ​

第四步：汇总答案！ ​

代码实现 ​

复杂度分析 ​

知识点总结 ​