题解 P3830 【[SHOI2012]随机树】
Scarlet_Hypoc
·
·
题解
这篇题解可能算是比较全面的了吧qwq
第一问比较简单，设 f[i] 表示有 i 个叶子的树的叶节点平均深度，那么总深度就是 f[i]\times i，要从 f[i-1] 转移到 f[i] 的话，就是随机选一个叶子节点，减去它的深度，然后加上 2\times (它的深度+1)，而它的期望深度就是 f[i-1]，所以有 f[i]=\frac {f[i-1]\times (i-1)-f[i-1]+2\times (f[i-1]+1)} i=f[i-1]+\frac 2 i。
第二问的话设 g[i][j] 表示有 i 个叶子的且深度大于等于 j 的树的出现概率。二叉树的比较经典的转移就是枚举根节点的左右子树大小了，这题就是枚举左右子树中叶子节点数量，于是有：
g[i][j]=\sum_{k=1}^{i-1} \frac {g[k][j-1]+g[i-k][j-1]-g[k][j-1]*g[i-k][j-1]} {i-1}
而下面的除以 $i-1$，即乘以 $\frac 1 {i-1}$，表示一棵有 $i$ 个叶子的树，左子树有 $k$ 个叶子的概率，证明也不难：
我们先不考虑求这个概率，先求 **一棵有 $i$ 个叶子的树，左子树有 $k$ 个叶子的情况数**，
由于树中有 $i$ 个叶子，所以这棵树已经被展开过 $i-1$ 次，去掉一开始的展开根节点，对左右子树一共展开了 $i-2$ 次，而其中有 $k-1$ 次展开的是左子树，有 $i-k-1$ 次展开的是右子树，那么显然有 $C_{i-2}^{k-1}$ 种不同的情况，即 $\frac {(i-2)!} {(k-1)!(i-k-1)!}$。
再考虑对一个节点展开 $p$ 次有多少种情况：
1、第一次展开只有 $1$ 个点能选择，一共有 $1$ 种不同的情况
2、第二次展开有 $2$ 个点能选择，一共有 $2$ 种不同的情况
3、第三次展开有 $3$ 个点能选择，一共有 $3$ 种不同的情况
……
所以一共有 $p!$ 种情况。
所以，被展开了 $k-1$ 次的左子树一共有 $(k-1)!$ 种不同的情况，右子树有 $(i-k-1)!$ 种，和 $\frac {(i-2)!} {(k-1)!(i-k-1)!}$ 乘起来，就得到了 **一棵有 $i$ 个叶子的数，左子树有 $k$ 个叶子的情况数**，而这个值，是 $(i-2)!$，与 $k$ 无关。
所以，无论 $k$ 是多少，情况数都是固定的，而一棵有 $i$ 个叶子的树的总情况数有 $(i-1)!$ 种，所以对于每个 $k$，出现的概率就是 $\frac {(i-2)!} {(i-1)!}=\frac 1 {i-1}$。
于是，求出 $g$ 数组后，最后的答案就是 $\sum_{j=1}^{n-1} f[n][j]$。
你可能会问，期望不应该等于概率乘权值吗？你这是概率的总和啊。
注意看上面的定义：**深度至少为 $j$**，这意味着，一棵 $n$ 个叶子深度为 $j$ 的树，在 $f[n][1],f[n][1],f[n][2],...,f[n][j]$ 中都被统计过，所以他的出现概率被统计了 $j$ 次，就相当于概率乘以深度 $j$ 了。
于是代码如下：
```cpp
#include <cstdio>
#define maxn 110
int type,n;
double f[maxn];
void work1()
{
for(int i=2;i<=n;i++)
f[i]=f[i-1]+2.0/i;
printf("%.6lf",f[n]);
}
double g[maxn][maxn],ans=0;
void work2()
{
for(int i=1;i<=n;i++)
g[i][0]=1;
for(int i=2;i<=n;i++)
for(int j=1;j<i;j++)
for(int k=1;k<i;k++)
g[i][j]+=(g[k][j-1]+g[i-k][j-1]-g[k][j-1]*g[i-k][j-1])/(i-1);
for(int i=1;i<n;i++)
ans+=g[n][i];
printf("%.6lf",ans);
}
int main()
{
scanf("%d %d",&type,&n);
if(type==1)work1(); else work2();
}
```
后来想了想，为什么 $g$ 数组的定义是深度至少为 $j$，而不能恰好为 $j$ 呢？
事实上，是可以的，但是复杂度就会从 $n^3$ 变成 $n^4$。
在转移的时候，先看左子树，假如左子树深度为 $j-1$，那么右子树的深度只能是 $1$ ~ $j-2$，假如右子树深度为 $j-1$，左子树深度就只能是 $1$ ~ $j-2$，或者两棵子树深度都是 $j-1$。
而 $1$ ~ $j-2$ 这部分就需要再来一个循环进行累加了（不过多处理一个前缀和数组事实上还是可以把复杂度变回 $n^3$ 了）。
最后统计答案的时候，就变成了 $\sum_{j=1}^{n-1}f[n][j]\times j$ 了。
代码如下：
```cpp
#include <cstdio>
#define maxn 110
int type,n;
double f[maxn];
void work1()
{
for(int i=2;i<=n;i++)
f[i]=f[i-1]+2.0/i;
printf("%.6lf",f[n]);
}
double g[maxn][maxn],ans=0;
void work2()
{
g[1][0]=1;
for(int i=2;i<=n;i++)
for(int j=1;j<i;j++)
for(int k=1;k<i;k++)
{
double tot1=0,tot2=0;
for(int l=0;l<=j-1;l++)tot1+=g[i-k][l];
for(int l=0;l<j-1;l++)tot2+=g[k][l];
g[i][j]+=(g[k][j-1]*tot1+g[i-k][j-1]*tot2)/(i-1);
}
for(int i=1;i<n;i++)
ans+=g[n][i]*i;
printf("%.6lf",ans);
}
int main()
{
scanf("%d %d",&type,&n);
if(type==1)work1(); else work2();
}
```