LOJ

分析

树相等于一个左部点是深度为奇数的点、右部点是深度为偶数的点的二分图。

首先需要在 $n-1$ 个点中选出 $k-1$ 个作为深度为奇数的点（$1$ 的深度一定为奇数）。

将深度为奇数的点作为左部点、深度为偶数的点作为右部点，两部分间两两连边，则问题变为求生成树个数。

考虑 Prufer 序列，则左部点出现了 $n-k-1$ 次、右部点出现了 $k-1$ 次，故生成树个数为 $k^{n-k-1}(n-k)^{k-1}$。当然也可以手算基尔霍夫矩阵

故答案为 ${n-1\choose k-1}k^{n-k-1}(n-k)^{k-1}$。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

int n,k,mod;
int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
    return c;
}
int fac(int n) { int s=1; for (int i=2;i<=n;++i) s=1ll*s*i%mod; return s; }
int C(int n,int m) {
    if (n<m) return 0;
    return 1ll*fac(n)*qpow(fac(m),mod-2)%mod*qpow(fac(n-m),mod-2)%mod;
}

int main() {
    n=read(),k=read(),mod=read();
    printf("%d\n",1ll*C(n-1,k-1)*qpow(k,n-k-1)%mod*qpow(n-k,k-1)%mod);
    return 0;
}