关键词：

P3830 随机树

坑题，别人的题解我看了一个下午没一个看得懂的，我还是太弱了。

题目链接 P3830 [SHOI2012]随机树

题目描述

输入输出格式

输入格式：

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

输出格式：

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

说明

第一问很水，考虑每次新拓展节点就是让树的总深度加上 2 

也就是: $$f[i]= dfracf[i-1]*(i-1) + f[i-1] + 2 i$$

意思就是原来 i-1 个节点的平均深度，乘上 (i-1) 变成深度和，然后再加一次 平均深度，然后加 2 ，除以 i 个叶子结点得到当前答案。

化简后式子就变成了: $$f[i]=f[i-1] + dfrac2 i $$

然后来到第二问（关键问题）。

首先这是概率期望 dp ，于是我们考虑设计状态。

那么我们让 $f[i][j]$ 表示 i 个叶子节点，深度为 j 的概率（是概率）。

那么转移就是： $$ f[i][j] = dfrac f[k][j-1] + f[i-k][j-1]-f[k][j-1] imes f[i-k][j-1] i-1 $$

其中 f[i][j] 表示新树状态，f[k][j-1] 为左子树状态，f[i-k][j-1] 为右子树状态。

很多题解到这儿就没了，就没了！也不解释一下的说（尤其 i-1 解释的是真草率）。

最后我自己口胡了一下大概可能也许想通了。

首先 f[i][j] 是我们现在构造出的树的状态，也就是说我们用两个子树拼凑出了一棵新树，而根是新加节点（新加节点会使得左右子树所有叶子结点深度均增加 1 ）。

所以这点很重要，也是尤其关键的一步，在强调一遍，f[i][j] 只是代表了新树的形态，且是已经确定了的形态。

那么形成这棵树的概率也就是上面的转移式了，左子树有 j-1 个节点的概率 + 右子树有 j-1 个节点的概率 - 左右子树同时有 j-1 个节点的概率（容斥）。

接着呢？ 我们考虑除去 i-1 的意义（自己的想法而已）：

我们让当前的这棵树回到上一个状态，也就是说我们令这棵树最后一次叶子结点的扩展取消，回到 i-1 的状态。 （请脑补）

然后聪明的你已经想出来了，这时候要达到当前状态的概率是？ 当然是 1/(i-1) 。因为当前这棵树删除的节点扩展回来的概率就是 1/(i-1)。

然后问题就解决了，放代码（非常短啊）。

 1 //by Judge
 2 #include<iostream>
 3 #include<cstdio>
 4 using namespace std;
 5 int q,n; double ans,f[111][111];
 6 int main() scanf("%d%d",&q,&n);
 7     if(q==1)
 8         for(int i=2;i<=n;++i) ans+=2.0/i;
 9         return printf("%.6lf
",ans),0;
10      f[1][0]=f[2][1]=f[3][2]=1;
11     for(int i=4;i<=n;++i) for(int j=1;j<=n;++j)
12         for(int k=0;k<j;++k) for(int l=0;l<i-j;++l)
13             f[i][max(k,l)+1]+=(f[j][k]*f[i-j][l])/(i-1);
14     for(int i=1;i<n;++i) ans+=f[n][i]*i; return printf("%.6lf
",ans),0;
15 

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

洛谷p4332[shoi2014]三叉神经树题解(代码片段)

一、题目：洛谷原题二、思路：这道题怎么说呢？只能说有点意思，让我第一次见识了LCT怎么应用。首先一个非常明显的性质，就是比如我现在修改了某个叶子结点，记为\\(leaf\\)，那么因此而状态发生改变的点一定是从\\(leaf\\)... 查看详情

[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。那么就分... 查看详情

洛谷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 查看详情

[shoi2008]堵塞的交通(代码片段)

...始完全没想到用线段树来维护这种网格的连通性，后来看题解之后发现实在是妙啊……（满足区间可合并性）线段树维护的是一段区间的四个端点间两两的连通信息，六个变量，合并时由于要考虑两块是否可合并，还得维护区间... 查看详情

题解-shoi2005树的双中心(代码片段)

SHOI2005树的双中心给树(T=(V,E)(|V|=n))，(w_u(uinV))。求(xinV,yinV:left(sum_uinVw_ucdotmin(dis_u,x,dis_u,y)ight)_min)。数据范围：(1lenle50000)，(1leT‘s~Heightle100)。一眼思路：把(T)由一条边砍成(T 查看详情

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

...经组织的输入变化情况。请你模拟SHOI组织的输出结果。题解身体啊。先考虑每一次修改能影响到的范围，这个比较简单，只能是这个点到根的路径上的所有点。再次进一步的考虑，发现能够影响到的范围是一段连续的区间。考... 查看详情

并不对劲的bzoj2521:p5039:[shoi2010]最小生成树(代码片段)

...定会在这张图的最小生成树上。(nleq500;mleq800;边权leq10^6;)题解在进行最小生成树时，边权具体是多少不重要，重要的是边之间的边权大小关系。所以可以把“除某边以外的所有边边权-1”看成“该边边权+1” 查看详情

题解p3252[jloi2012]树(代码片段)

(Huge[JLOI2012]树)题目描述在这个问题中，给定一个值S和一棵树。在树的每个节点有一个正整数，问有多少条路径的节点总和达到S。路径中节点的深度必须是升序的。假设节点1是根节点，根的深度是0，它的儿子节点的深度为1。路... 查看详情