Codeforces 280C Game on Tree 概率dp 树上随机删子树 求删完次数的期望

题目链接:点击打开链接

题意:给定n个点的一棵树

每次操作随机选任意一个点,把这个点和这个点的子树删去。

当把所有点删去则停止。

问操作次数的期望。

题解引用自:点击打开链接

删除的规则拥有一个非常好的性质:对于任意(u,v),选择u会导致删除v,那么选择u会删除的点集合一定包含选择了v以后会删除的点集合。

我们考虑换一种方式来实现删除的过程:
产生一个随机的1-n的排列P,从前往后依次尝试删除这些点,如果当前点已经被删除,就什么都不干,否则把次数+1,删除这个点以及他的所有后代。

通过这种方式产生的实际删除序列与题目原来规定的方式的概率分布是相同的。这一点是比较显然且非常容易证明的。

如果我们自己YY出来的过程进行了一半,排列P还有一个后缀等待解释,这个后缀中1到n号是实际仍然留在树中的点,n+1到 n+k号是实际已经不存在的点。那么1号点是下一次被选择的点的概率是

由于之前我们发现的性质,上述过程也可以这样说:

产生一个随机的1-n的排列P,从前往后删除这些点,如果当前点未删除,把次数+1,之后无条件删除这个点以及他的所有后代。
(与原先那个的区别,尝试YY几个类似的删东西的题目,然后尝试用这种方法做就能体会了。。)

这有什么用呢?由期望的线性性,我们最后要计算的是E(总操作次数)=sigma{E([每个结点u是因为选中了自己而删去的])},之后那个谓词成立当且仅当在我们生成的排列P中,u出现在他所有的祖先之前,因此这一项的期望值就是u在树中深度的倒数。把所有深度倒数加起来就是答案。

#include template inline bool rd(T &ret) { char c; int sgn; if(c=getchar(),c==EOF) return 0; while(c!='-'&&(c'9')) c=getchar(); sgn=(c=='-')?-1:1; ret=(c=='-')?0:(c-'0'); while(c=getchar(),c>='0'&&c inline void pt(T x) { if (x 9) pt(x/10); putchar(x%10+'0'); } using namespace std; const int N = 100005; struct Edge{ int to, nex; }edge[N>u>>v; add(u, v); add(v, u); } } int main(){ ios::sync_with_stdio(false); while(cin>>n){ input(); dfs(1,1,1); double ans = 0; for(int i = 1; i

点击复制链接 与好友分享!回本站首页
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力
上一篇:hdu 5113 Black And White, 黑白染色,技巧
下一篇:hdu3016——Man Down
相关文章

HDU 3853 LOOPS 概率dp入门 (1)

poj-2151-概率dp

简单概率dp-hdu-4487-Maximum Random

hdu 4487 概率dp Maximum Random Walk

概率dp-hdu-4089-Activation

HDU 4465 - Candy(概率与数学优化)

概率dp-九度-1546-迷宫问题

poj-3071-Football-概率模拟

HDU 4762 Cut the Cake(概率+推理

poj 3744 Scout YYF I (矩

图文推荐

Codeforces 280C Game on Tree 概率dp 树上随机删子树 求删完次数的期望
ZOJ 3640 Help Me
Codeforces 280C Game on Tree 概率dp 树上随机删子树 求删完次数的期望
CF 518C(Anya and
Codeforces 280C Game on Tree 概率dp 树上随机删子树 求删完次数的期望
hdu 1016 Prime R
UVA - 11987 - A

分类:默认分类 时间:2015-03-07 人气:8
本文关键词:
分享到:

相关文章

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.083 (s). 10 q(s)