「雅礼集训 2018 Day1」树 题解

思路

注意到对于一棵树，结点 1 一定是结点 2 的父亲，那么树的最大深度一定是这两者的子树之一（此处结点 1 的子树不包含结点二的子树，此后结点 1 的子树简称为 A，结点 2 的子树简称为 B）。

设 $dp_{i,j}$ 表示有 $i$ 个结点时最大深度为 $j$ 的方案数。

当最深的结点在 A 内时，有 $dp_{i,j}=dp_{s,j}\times dp_{i-s,t}\times \binom{i-2}{s-1}$，其中 $dp_{s,j}$ 是A，$dp_{i-s,t}$ 是B，有 $t<j$（深度最深的在A），$\binom{i-2}{s-1}$ 表示在除了两个根节点外的点中选择 $s-1$ 个作为A的方案数。

当最深的结点在 B 内时，有 $dp_{i,j}=dp_{s,t}\times dp_{i-s,j-1}\times \binom{i-2}{s-1}$，其中 $dp_{s,t}$ 是A，$dp_{i-s,j-1}$ 是B（此处 $j-1$ 是因为还要加上 1，2 之间的边），有 $t<j$（深度最深的在B），$\binom{i-2}{s-1}$ 同理。

最终答案即为 $\frac{\sum_{i=2}^{n}dp_{n,i}\times i}{(n-1)!}$

设 $ans=\sum_{i=2}^{n}dp_{n,i}\times i,div=(n-1)!$，在四舍五入时等价于 $\lfloor\frac{2\times\frac{ans}{div}+1}{2}\rfloor=\lfloor\frac{2\times ans+div}{2\times div}\rfloor$

代码

#include<bits/stdc++.h>
using namespace std;
typedef __int128 ll;
int n,mod;
ll qpow(ll a,ll b){
	ll ans=1;
	for(;b;b>>=1,a=a*a%mod)if(b&1)ans=ans*a%mod;
	return ans;
}
ll C[33][33]; 
ll dp[33][33];
void pr(ll x){
	if(x/10)pr(x/10);
	putchar(x%10+'0');
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>mod;
	if(n==1){
		cout<<"1\n1";
		return 0;
	}
	for(int i=0;i<=n;i++)C[i][i]=1;//预处理组合数 
	for(int i=1;i<=n;i++){
		for(int j=0;j<i;j++){
			C[i][j]=C[i-1][j-1]+C[i-1][j];
		}
	}
	dp[1][1]=1;
	for(int i=2;i<=n;i++){
		for(int j=1;j<=n;j++){
			for(int s=1;s<i;s++){
				for(int t=1;t<j;t++)dp[i][j]=(dp[i][j]+dp[s][j-1]*dp[i-s][t]*C[i-2][s-1]);//深度最深的在A 
				for(int t=1;t<=s&&t<j;t++)dp[i][j]=(dp[i][j]+dp[s][t]*dp[i-s][j]*C[i-2][s-1]);//深度最深的在B 
			}
		}
	}
	ll ans=0,div=1;
	double res=0;
	for(int i=2;i<n;i++)div=div*i;
	for(int i=2;i<=n;i++)ans=(ans+dp[n][i]*i);
	pr((ans*2+div)/div/2);putchar('\n');//四舍五入 
	pr(ans%mod*qpow(div%mod,mod-2)%mod);
	return 0;
}