CF280C # Game on Tree 期望的可加性
期望
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);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/322943.html
標籤：C++
上一篇：用c#搜索txt檔案中的字串