CF280C # Game on Tree 期望的可加性
期望
题目描述
给定一棵有根树，结点编号从 1 到 n。根结点为 1 号结点。
对于每一次操作，等概率的选择一个尚未被删去的结点并将它及其子树全部删去。当所有结点被删除之后，游戏结束；也就是说，删除 1 号结点后游戏即结束。
要求求出删除所有结点的期望操作次数。
我们可以发现本题求的是删除总次数的期望，而根本无法直接求出，简单转换为求出每一个点的期望选择次数并且累和，即：
[del(all space tree)= sum_{i=1}^{n} P(i)
]
我们可以想象成无论一个点是否删除它都存在在一个包含了所以点的序列上，所以一个点被删除当且仅当它在所以他的祖先节点后面，所以选择成功的概率为$ frac{1}{dep(i)}qquad $
所以我们可以简单搞定了：
(cose:)
#include<bits/stdc++.h>
#define ll long long
#define fd(i, a, b) for (ll i = a; i >= b; i--)
#define r(i, a) for (ll i = fir[a]; i; i = e[i].nex)
#define file(a) freopen(#a ".in", "r", stdin);freopen(#a ".out", "w", stdout);
#define il inline
#define gc getchar()
#define f(i,a,b) for(ll i=a;i<=b;i++)
using namespace std;
const ll maxn=1e5+10,INF=1e16;
il ll read(){
ll x=0,f=1;char ch=gc;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc;}
while(ch>='0'&&ch<='9') x=(x*10)+(ch^48),ch=gc;
return x*f;
}
ll dep[maxn],n;
vector<ll> e[maxn];
il void add(ll a,ll b){e[a].push_back(b);}
il void dfs(ll v,ll f){
dep[v]=dep[f]+1;
f(i,0,e[v].size()-1){
ll t=e[v][i];
if(t==f) continue;
dfs(t,v);
}
}
double ans;
int main()
{
n=read();
f(i,2,n){ll a=read(),b=read();add(a,b);add(b,a);}
dfs(1,0);
f(i,1,n) ans+=(1.0/double(dep[i]));
printf("%.10lf",ans);
}
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
