#C241111E. CF280C-Game on Tree

标签（Label）

期望
数学

网址（Website）

Problem - 280C - Codeforces

Game on Tree - 洛谷

题目（Problem）

题目描述

给定一棵有根树，结点编号从 $1$ 到 $n$。根结点为 $1$ 号结点。

对于每一次操作，等概率的选择一个尚未被删去的结点并将它及其子树全部删去。当所有结点被删除之后，游戏结束；也就是说，删除 $1$ 号结点后游戏即结束。

要求求出删除所有结点的期望操作次数。

输入格式

第一行，一个正整数 $n$ 表示结点数量。

接下来 $n-1$ 行每行两个数，表示树上的一条连接 $a_i$ 与 $b_i$ 的边 $(a_i,b_i)$

保证给定的数据是一棵树。

输出格式

输出一个实数，表示期望操作次数。答案误差在 $10^{-6}$ 之内则认为正确。

样例 #1

样例输入 #1

2
1 2

样例输出 #1

1.50000000000000000000

样例 #2

样例输入 #2

3
1 2
1 3

样例输出 #2

2.00000000000000000000

样例解释

在第一个样例中，有两种情况：

一种是直接删除根（即 $1$ 号结点），另一种是先删去 $2$ 号结点，再删除 $1$ 号结点。

操作次数的期望是 $1\times \dfrac12+2\times\dfrac12=1.5$。

在第二个样例中，情况更为复杂。其中有两种情况会将问题转化成第一个样例，而剩下的一种情况会一次全部删除。

操作次数的期望是 $1\times\dfrac13+(1+1.5)\times\dfrac23=\dfrac13+\dfrac53=2$。

题解（Solution）

$\qquad$答案为 $\sum_{i=1}^{i\le n}\frac{1}{dep_i}$ ，可以看看洛谷的题解。

代码（Code）

#include<bits/stdc++.h>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i++)
using namespace std;
#define P pair<int,int> 
#define int long long
#define x first
#define y second
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 1012345;
bool ST;
double Tim;

vector<int> ft[N];
int n,dep[N];
double ans;

void dfs(int x,int fa){
	dep[x] = dep[fa]+1;
	for(auto y:ft[x])
		if(y^fa) dfs(y,x);
}

void Solve(){
	n=rd();For(i,1,n-1){
		int x=rd(),y=rd();
		ft[x].emplace_back(y);
		ft[y].emplace_back(x);
	}dfs(1,0);
	For(i,1,n) ans += 1./dep[i];
	printf("%.15lf\n",ans);
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	int Tt=1;Tim=clock();
	while(Tt--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}