题目大意

给定节点数 $N$，要求构造一棵以 $1$ 为根的有根树，使得深度为奇数的节点恰好有 $K$ 个。求不同的有根树数量对 $P$ 取模的结果。

关键点：

• 深度定义为从节点到根路径上的节点个数（包括端点），因此根节点深度为 1（奇数）
• 两棵树不同当且仅当它们的边集不同

解题思路

这是一个经典的有根树计数问题，需要用到生成函数和树形DP的思想。

问题转化

设 $f_n$ 表示 $n$ 个节点的有根树数量，其中深度为奇数的节点有 $m$ 个。

我们可以通过生成函数来求解。设：

• $F_0(x)$ 表示根节点深度为偶数（但实际上根节点深度为1，是奇数，所以这里需要小心处理）
• $F_1(x)$ 表示根节点深度为奇数的生成函数

但实际上更直接的方法是：设 $f_i$ 表示 $i$ 个节点的有根树数量，$g_i$ 表示 $i$ 个节点的有根树中深度为奇数的节点数为指定值的方案数。

核心递推

考虑树的递归结构：一棵有根树由根节点和若干子树组成。

设 $dp[n][k]$ 表示 $n$ 个节点的有根树中，深度为奇数的节点恰好为 $k$ 个的方案数。

转移时，我们考虑根节点的子树。由于根节点深度为1（奇数），所以：

• 根节点本身贡献 1 个奇数深度节点
• 剩下的 $n-1$ 个节点分配到各个子树中
• 对于子树，根节点的深度相对于原树的根是偶数

这实际上形成了一个交替奇偶的结构。

生成函数解法

设 $F(x,y)$ 是二元生成函数，其中 $x$ 记录节点数，$y$ 记录奇数深度节点数。

根据有根树的递归定义，我们有：

$$F(x,y) = x \cdot y \cdot \exp\left(\sum_{i=1}^\infty \frac{G(x^i, y^i)}{i}\right) $$

其中 $G(x,y)$ 是偶数深度为根的树的生成函数，且 $G(x,y) = x \cdot \exp\left(\sum_{i=1}^\infty \frac{F(x^i, y^i)}{i}\right)$

通过解这个方程组，我们可以得到最终的答案。

实际实现

对于大规模数据（$N \leq 500000$），需要使用生成函数和多项式技术。具体步骤：

1. 先求出 $n$ 个节点的有根树数量（Cayley公式：$n^{n-2}$，但这里是有根树，所以是 $n^{n-1}$）
2. 考虑奇偶深度的分布：实际上这是一个组合问题，可以用生成函数解决
3. 最终答案可以表示为组合数的形式

关键结论：对于 $n$ 个节点的有根树，深度为奇数的节点数为 $k$ 的方案数为：

$$\binom{n-1}{k-1} \cdot (k)^{k-2} \cdot (n-k)^{n-k-1} $$

其中：

• $\binom{n-1}{k-1}$：选择哪些节点是奇数深度（根节点固定为奇数深度）
• $(k)^{k-2}$：奇数深度节点形成的树的方案数
• $(n-k)^{n-k-1}$：偶数深度节点形成的树的方案数

代码实现

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll n, k, P;

ll qpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % P;
        a = a * a % P;
        b >>= 1;
    }
    return res;
}

ll solve() {
    // 答案为 C(n-1, k-1) * (k)^(k-2) * (n-k)^(n-k-1) mod P
    
    // 计算组合数 C(n-1, k-1)
    ll comb = 1;
    for (ll i = 1; i <= k - 1; i++) {
        comb = comb * (n - i) % P;
        comb = comb * qpow(i, P - 2) % P;
    }
    
    // 计算 k^(k-2)
    ll term1 = (k <= 1) ? 1 : qpow(k, k - 2);
    
    // 计算 (n-k)^(n-k-1)
    ll term2 = (n - k <= 1) ? 1 : qpow(n - k, n - k - 1);
    
    return comb * term1 % P * term2 % P;
}

int main() {
    cin >> n >> k >> P;
    cout << solve() << endl;
    return 0;
}

复杂度分析

• 计算组合数：$O(k)$
• 快速幂：$O(\log n)$
• 总复杂度：$O(k + \log n)$，对于 $n \leq 500000$ 可以接受

总结

本题的关键在于发现树的奇偶深度分布的组合结构，将问题转化为在 $n-1$ 个非根节点中选择 $k-1$ 个作为奇数深度节点，然后分别计算奇数深度节点和偶数深度节点形成的树的方案数。最终答案可以用简洁的组合表达式表示。