洛谷P3830 [SHOI2012]随机树 题解

题目链接：P3830 [SHOI2012]随机树

题意：

给定一棵随机有根二叉树的叶节点数 $n$ ，求

1. 叶子结点深度的期望
2. 树深度的期望（根节点深度为 $0$ ）

每组数据将给出 $\mathtt{op=1/2}$ ，表示询问的子问题。

随机方式如下

1. 初始只有根节点
2. 每次选择一个叶结点，为其添加两个子结点
3. 重复步骤 2 （共 $n-1$ 次），得到一棵随机树。

例如下图为 $n=5$ 的一种生成方式。

输入格式：

输入仅有一行，包含两个正整数 $\mathtt{op},n$ ，分别表示问题编号以及叶结点的个数。

输出格式:

输出仅有一行，包含一个实数 $d$，四舍五入精确到小数点后 $6$ 位。如果 $\mathtt{op = 1}$，则 d 表示叶结点平均深度的数学期望值；如果 $\mathtt{op = 2}$ ，则 $d$ 表示树深度的数学期望值。

数据范围：

$\mathtt{op=1/2}, ~2 \le n \le 100$ 。

注意到生成这棵树的方式于叶结点数量有关，因此可以围绕叶结点设计状态。

首先第一问，设 $f_i$ 表示 $i$ 个叶子结点的树的「叶子结点深度期望」，则总深度为 $i\times f_i$ 。

考虑在 $i-1$ 个叶子结点的树中随机展开一个叶子，那么深度总和会增加 $f_{i-1} + 2$ ，则

$$f_i = \frac{1}{i}\times \left[f_{i-1}\times (i-1) + f_{i-1} + 2\right] = f_{i-1} + \frac{2}{i}$$

然后第二问。设 $f_{i,j}$ 表示 $i$ 个叶子结点的树，深度大于等于 $j$ 的概率。则最终答案为 $\sum_{i=1}^{n-1}f_{n,i}$ 。

注：记 $p_i$ 表示 $n$ 个叶子结点的树深度为 $i$ 的概率，则 $\sum_{i=1}^{n-1}f_{n,i} = \sum_{i=1}^{n-1}p_i\times i$ 。

考虑转移，这里需要用到基本的容斥原理。下面的 $\frac{1}{i-1}$ 是每一种情况的出现概率

$$f_{i,j} = \sum_{k=1}^{i-1} \frac{1}{i-1}\times(f_{k,j-1} + f_{i-k,j-1} - f_{k,j-1}f_{i-k,j-1})$$

时间复杂度 $\mathcal{O}(n^2)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(115))

int op,n;
double res,f[N][N];
double solve(double a,double b) { return a + b - a * b; }
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cout << fixed << setprecision(6);
    cin >> op >> n;
    if(op == 1)
    {
        for(int i=2; i<=n; i++) res += 2.0 / i;
        return cout << res << '\n', 0;
    }
    for(int i=1; i<=n; i++) f[i][0] = 1;
    for(int i=2; i<=n; i++)
        for(int j=1; j<i; j++)
        {
            for(int k=1; k<i; k++)
                f[i][j] += solve(f[k][j-1], f[i-k][j-1]);
            f[i][j] /= (i-1);
        }
    for(int i=1; i<n; i++) res += f[n][i]; cout << res << '\n';
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/blog/Fizzmy/solution-p3830