关键词：

P3830 [SHOI2012]随机树

链接

分析：　

　　第一问：f[i]表示有i个叶子结点的时候的平均深度，$f[i] = \fracf[i - 1] + 2 + f[i - 1] * (i - 1)2 $，表示新增加一个叶子结点，深度增加2，加权后取平均值。

　　第二问：f[i][j]表示有i个叶子结点，树的深度大于等于j的概率，有$f[i][max(k, l)+ 1] = \fracf[j][k] \times f[i - j][l]i - 1$，$ans=\sum\limits_i = 1^n i * f[n][i]$。

　　其中除以$i-1$表示i个叶子结点中，左儿子为j个时候的概率。因为左儿子结点只有$i-1$个取值，于是每个的概率都是$\frac1i-1$。

　　枚举完左儿子的叶子结点，右儿子叶子结点也就确定了，然后左右儿子结点都是一个相同的子问题。

代码：

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cctype>
#include<set>
#include<queue>
#include<map>
#include<vector>
#include<bitset>
using namespace std;
typedef long long LL;

inline int read() 
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch==‘-‘)f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-‘0‘;return x*f;


const int N = 1005;
void solve1(int n) 
    static double f[N];
    for (int i = 2; i <= n; ++i) f[i] = f[i - 1] + 2.0 / i;
    printf("%.6lf\n", f[n]);

void solve2(int n) 
    static double f[N][N];
    f[1][0] = 1.0;
    for (int i = 2; i <= n; ++i) 
        for (int j = 1; j < i; ++j) 
            for (int k = 0; k <= j; ++k)
                for (int l = 0; l <= (i - j); ++l) 
                    f[i][max(k, l) + 1] += f[j][k] * f[i - j][l] / (i - 1);
    double ans = 0;
    for (int i = 1; i <= n; ++i) ans += i * f[n][i];
    printf("%.6lf\n", ans);

int main() 
    int ty = read(), n = read();
    ty == 1 ? solve1(n) : solve2(n);    
    return 0;

bzoj2830&洛谷3830：[shoi2012]随机树——题解(代码片段)

https://www.luogu.org/problemnew/show/P3830#sub  <-题面看这里~https://www.lydsy.com/JudgeOnline/problem.php?id=2830感觉智商被压制了的一题……后面放吐槽。参考：https://www.cnblogs.com/GuessYCB/p/846249 查看详情

洛谷3830[shoi2012]随机树概率dp(代码片段)

题目输入格式输入仅有一行，包含两个正整数q,n，分别表示问题编号以及叶结点的个数。输出格式输出仅有一行，包含一个实数d，四舍五入精确到小数点后6位。如果q=1，则d表示叶结点平均深度的数学期望值；如果q=2，则d表示... 查看详情

luogup3830[shoi2012]随机树期望概率+动态规划+结论(代码片段)

题意非常的复杂，考虑转化一下：每次选择一个叶节点，删除本叶节点（深度为$dep$）的同时，加入两个深度为$dep+1$的叶节点，重复$n$轮首先考虑第$1$问，（你看我这种人相信数据绝对是最大的数据，直接$f[i][S]$表示$i$个叶子结... 查看详情

[shoi2012]魔法树(代码片段)

[题目链接]    https://www.lydsy.com/JudgeOnline/problem.php?id=2836[算法]    树链剖分    时间复杂度:O(NlogN^2)[代码]    #include<bits/ 查看详情

[shoi2012]随机树

题面在这里题意随机生成一棵(n)个叶节点的二叉树,方法是从根节点开始,每次等概率选择一个叶子节点(一开始根节点同时也是叶子节点)并生成其左右儿子(称为一次展开),直到该树有(n)个叶节点为止给定(nleq100),求其叶节点平均深... 查看详情

p4340[shoi2016]随机序列(线段树)(代码片段)

P4340[SHOI2016]随机序列(线段树)结论：只有前缀积有贡献。因为第一个数前面是没有符号的，除了前缀积外，都可以通过加号变成减号、减号变加号使其贡献抵消。接下来考虑每个前缀积的贡献。我们可以枚举前缀积的... 查看详情

[shoi2012]随机树(代码片段)

感觉第一问就非常神仙，还有第二问怎么被我当成组合数学题来做了首先是第一问期望具有线性性，于是深度平均值的期望等于深度和的期望值的平均设(dp_x)表示具有(x)个叶子节点的树的深度和的期望值是多少我们发现扩展一个... 查看详情

luogup3830[shoi2012]随机树期望dp(代码片段)

LINK：随机树非常经典的期望dp.考虑第一问：设f[i]表示前i个叶子节点的期望平均深度。因为期望具有线性性所以可以由每个叶子节点的期望平均深度得到总体的。(f[i]=(f[i-1]cdot(i-1)+(f[i-1]+1)cdot2-f[i-1])/i=f[i-1]+2/i)考虑第二问：可以设... 查看详情

p3833[shoi2012]魔法树(代码片段)

DescriptionHarryPotter新学了一种魔法：可以让改变树上的果子个数。满心欢喜的他找到了一个巨大的果树，来试验他的新法术。这棵果树共有N个节点，其中节点0是根节点，每个节点u的父亲记为fa[u]，保证有fa[u]<u。初始时，这棵... 查看详情

luogu3833shoi2012魔法树(代码片段)

题目描述HarryPotter新学了一种魔法：可以让改变树上的果子个数。满心欢喜的他找到了一个巨大的果树，来试验他的新法术。这棵果树共有N个节点，其中节点0是根节点，每个节点u的父亲记为fa[u]，保证有fa[u]<u。初始时，这棵... 查看详情

p3833[shoi2012]魔法树(代码片段)

简单的树链剖分，自己随便弄个样例就能过。给你一个树，支持两个操作：从u点到v点的路径上的点的权值都添加上d。查询以u点为根的子树的权值和。唯一可能错的就是1操作了。u到v的路径，显然需要找出他们的lca。那么就分... 查看详情

shoi2016随机序列(代码片段)

给你一个数列，在相邻两个数之间插入加号，减号或乘号每次支持单点修改，求所有这样可以得到的表达式之和，膜1e9+7sol：我是个sb。。。可以发现，如果某位置出现了加号，后面一定有一个减号把它消掉，于是答案就是一些... 查看详情

bzoj4597[shoi2016]随机序列线段树

【BZOJ4597】[Shoi2016]随机序列Description你的面前有N个数排成一行。分别为A1,A2,…,An。你打算在每相邻的两个Ai和Ai+1间都插入一个加号或者减号或者乘号。那么一共有3^(n-1)种可能的表达式。你对所有可能的表达式的值的和非常感... 查看详情

洛谷3833shoi2012魔法树

【题解】　　树链剖分模板题。。#include<cstdio>#include<algorithm>#include<queue>#defineN500010#definergregister#definels(u<<1)#definers(u<<1|1)#definemid((a[u].l+a[u].r)>>1)#defin 查看详情

p2161[shoi2009]会场预约-线段树染色(代码片段)

是真的染色，把不同预约看做不同颜色，现在问题就是一个区间内不同颜色的数量，这个分块线段树都能做吧（不考虑复杂度用莫队也行）注意，线段树的最大边界必须是定值，不能随输入改变（一开始懒得离线动态更新右端点... 查看详情

[bzoj1937][shoi2004]mst最小生成树(km算法,最大费用流)(代码片段)

1937:[Shoi2004]Mst最小生成树TimeLimit:3Sec  MemoryLimit:64MBSubmit:802  Solved:344[Submit][Status][Discuss]DescriptionInput第一行为N、M，其中表示顶点的数目，表示边的数目。顶点的编号为1、2、3、……、N-1、N。接下 查看详情

[shoi2014]三叉神经树(代码片段)

Description：计算神经学作为新兴的交叉学科近些年来一直是学术界的热点。一种叫做SHOI的神经组织因为其和近日发现的化合物SHTSC的密切联系引起了人们的极大关注。SHOI组织由若干个SHOI细胞构成,SHOI细胞之间形成严密的树形结构... 查看详情

p4412[shoi2004]最小生成树(代码片段)

传送门不难发现，对于每一条树边肯定要减小它的权值，对于每一条非树边要增加它的权值对于每一条非树边(j)，他肯定与某些树边构成了一个环，那么它的边权必须大于等于这个环上的所有边设其中一条边为(i)，变化量为(x)，... 查看详情