题目概述

有 $n$ 个点的树，$1$ 为根，每个节点的深度定义为到根的点数。求深度为奇数的点恰好为 $K$ 的树的个数。

解题报告

emm……我们把树按照深度奇偶分开，就变成了一个二分图，两边点数为 $K,n-K$ 。

然后就是求这个完全二分图的生成树个数……直接上结论：$K^{n-K-1}(n-K)^{K-1}$ 。

所以答案就是 ${n-1\choose K-1}K^{n-K-1}(n-K)^{K-1}$ 。

示例程序

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=500000;

int n,K,MOD,fac[maxn+5],INV[maxn+5],c[1005][1005];

inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
inline void Make(int n){
    INV[0]=INV[1]=1;for (int i=2;i<=n;i++) INV[i]=(LL)(MOD-MOD/i)*INV[MOD%i]%MOD;
    fac[0]=1;for (int i=1;i<=n;i++) fac[i]=(LL)fac[i-1]*i%MOD,INV[i]=(LL)INV[i-1]*INV[i]%MOD;
    for (int i=c[0][0]=1;i<=1000&&i<=n;i++) for (int j=c[i][0]=1;j<=i;j++) AMOD(c[i][j]=c[i-1][j],c[i-1][j-1]);
}
inline int C(int x,int y){
    if (x<y) return 0;if (x<=1000&&y<=1000) return c[x][y];
    return (LL)fac[x]*INV[y]%MOD*INV[(x)-(y)]%MOD;
}
inline int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=(LL)w*w%MOD) if (b&1) s=(LL)s*w%MOD;return s;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d%d",&n,&K,&MOD);Make(n);
    printf("%lld\n",(LL)C(n-1,K-1)*Pow(K,n-K-1)%MOD*Pow(n-K,K-1)%MOD);return 0;
}