洛谷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