题目分析：
思路不难想，考虑三个dp状态$f,g,d$。
$g[i]$表示有$i$个点的堆的数量
$d[i]$表示有$i$个点的情况下所有的方案数中点到根的距离和
$f[i]$表示要求的答案。
不难发现$g[i]=i!$，然后$d[i]$就枚举左子树大小，然后把左右子树单独的$d[j]$加起来，最后对于每种方案都加上$i-1$，也就是$d[i] = g[i]*(i-1)+\sum_{j=0}^{i-1}\binom{i-1}{j}*(d[j]*g[i-j-1]+d[i-j-1]*g[j])$。
然后考虑$f[i]$，也是考虑左子树大小然后递归处理$f[j]$，然后再通过$d[i]$处理出到根的距离和，最后再通过$d[i]$之间的乘法求出跨越两个子树的情况，具体看我代码。
代码：
#include<bits/stdc++.h>
using namespace std; const int maxn = ; int n,p;
int g[maxn],f[maxn],d[maxn];
int C[maxn][maxn]; void work(){
g[] = ; d[] = d[] = ;
for(int i=;i<=n;i++) g[i] = 1ll*g[i-]*i%p;
for(int i=;i<=n;i++){
for(int j=;j<i;j++){
int sub=1ll*C[i-][j]*((1ll*d[j]*g[i-j-]+1ll*d[i--j]*g[j])%p)%p;
d[i] += sub; d[i] %= p;
}
d[i] += 1ll*g[i]*(i-)%p; d[i] %= p;
}
f[] = ; f[] = ;
for(int i=;i<=n;i++){
for(int j=;j<i;j++){
int sub=1ll*C[i-][j]*(1ll*f[j]*g[i-j-]%p+1ll*f[i-j-]*g[j]%p)%p;
int lt=1ll*C[i-][j]*((d[j]+1ll*g[j]*j)%p)%p*g[i-j-]%p;
int rt=1ll*C[i-][j]*((d[i-j-]+1ll*g[i-j-]*(i-j-))%p)%p*g[j]%p;
int crs=1ll*lt*(i--j)%p,cts=1ll*rt*j%p;
f[i] += (1ll*sub+lt+rt+crs+cts)%p;
f[i] %= p;
}
}
printf("%d\n",f[n]);
} int main(){
scanf("%d%d",&n,&p);
if(p == ){puts("");return ;}
for(int i=;i<=n;i++){
C[i][] = C[i][i] = ;
for(int j=;j<i;j++){
C[i][j] = (C[i-][j] + C[i-][j-])%p;
}
}
work();
return ;
}