P3830 [SHOI2012]随机树
斯德哥尔摩
2018-10-06 00:38:25
[P3830 [SHOI2012]随机树](https://www.luogu.org/problemnew/show/P3830)
第一问很好处理：
设$f_x$表示有$x$个叶子节点的树的叶子节点平均深度。
我们考虑在一个有$x-1$个叶子节点的树里随机选择一个叶子节点展开，那么树的叶子节点深度总和会增加$f_{x-1}+2$。
所以：$$f_x=\frac {f_{x-1}\times(x-1)+f_{x-1}+2}{x}=f_{x-1}+\frac{2}{x}$$
第二问就比较难受了：
首先我们知道一个式子：
$$E(x)=\sum_{i=1}^{+}P(i\leq x)$$
说人话就是随机变量$x$的期望为对于所有$i$，$i\leq x$的概率之和。
我们设$dp[i][j]$表示有$i$个叶子，树的深度$\geq j$的概率。
转移时枚举左右子树有多少个叶子：
$$dp[i][j]=\sum_{k=1}^{i-1}\frac{1}{i-1}(dp[k][j-1]+dp[i-k][j-1]-dp[k][j-1]\times dp[i-k][j-1])$$
括号里的式子含义：
左右只要一边深度$\geq j-1$即可，所以式子展开其实是$dp[k][j-1]\times 1+dp[i-k][j-1]\times 1$，但这样会计算两次两边都$\geq j-1$的情况，所以需要减掉。
算是一个容斥吧。
最后答案即为：$$\sum_{i=1}^{n-1}dp[n][i]$$
附代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 110
using namespace std;
int id,n;
double f[MAXN],dp[MAXN][MAXN];
inline int read(){
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
void work_one(){
f[1]=0;
for(int i=2;i<=n;i++)f[i]=f[i-1]+2.00/i;
printf("%.6lf\n",f[n]);
}
void work_two(){
double ans=0;
for(int i=1;i<=n;i++)dp[i][0]=1;
for(int i=2;i<=n;i++)
for(int j=1;j<i;j++){
for(int k=1;k<i;k++)dp[i][j]+=dp[k][j-1]+dp[i-k][j-1]-dp[k][j-1]*dp[i-k][j-1];
dp[i][j]/=1.00*(i-1);
}
for(int i=1;i<n;i++)ans+=dp[n][i];
printf("%.6lf\n",ans);
}
void init(){
id=read();n=read();
}
int main(){
init();
if(id==1)work_one();
else work_two();
return 0;
}
```