CF280 C. Game on Tree

大佬教程收集整理的这篇文章主要介绍了CF280 C. Game on Tree，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

题目传送门：https://codeforces.com/problemset/problem/280/C

---

Description Momiji has got a rooted tree, consisTing of (n) nodes. The tree nodes are numbered by Integers from 1 to (n). The root has number 1. Momiji decided to play a game on this tree.

The game consists of several steps. On each step, Momiji chooses one of the remaining tree nodes (let's denote it by (v)) and removes all the subtree nodes with the root in node (v) from the tree. Node (v) gets deleted as well. The game finishes when the tree has no nodes left. In other words, the game finishes after the step that chooses the node number 1.

Each time Momiji chooses a new node uniformly among all the remaining nodes. Your task is to find the expectation of the number of steps in the described game.

Input The first line contains Integer (n (1 leqslant n leqslant 10^5)) — the number of nodes in the tree. The next (n) - 1 lines contain the tree edges. The (i)-th line contains Integers (a_i, b_i (1 leqslant a_i, b_i leqslant n; a_i neq b_i)) — the numbers of the nodes that are connected by the (i)-th edge.

it is guaranteed that the given graph is a tree.

Output Print a single real number — the expectation of the number of steps in the described game.

The answer will be considered correct if the absolute or relative error doesn't exceed (10^{- 6}).

Sample Input 1

2
1 2

Sample Output 1

1.50000000000000000000

Sample Input 2

3
1 2
1 3

Sample Output 2

2.00000000000000000000

---

每次删除一个节点时，会将其与其子树全部删除。故一个点被删除，当且仅当它到根的路径上的点被删除，即所有的情况数为(D_i)（(D_X)表示节点(X)的深度），故删除该点的概率为(frac{1}{D_i})

又因为每次删点的步数贡献为1，故答案为(sumlimits_{x}frac{1}{D_x})

/*program from Wolfycz*/
#include<map>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cString>
#include<iostream>
#include<algorithm>
#define Fi first
#define Se second
#define ll_inf 1e18
#define MK make_pair
#define sqr(X) ((X)*(X))
#define pii pair<int,int>
#definE int_inf 0x7f7f7f7f
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
inline char gc(){
	static char buf[1000000],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
template<typename T>inline T frd(T X){
	int f=1; char ch=gc();
	for (;ch<'0'||ch>'9';ch=gc())	if (ch=='-')    f=-1;
	for (;ch>='0'&&ch<='9';ch=gc())	x=(x<<1)+(x<<3)+ch-'0';
	return x*f;
}
template<typename T>inline T read(T X){
	int f=1; char ch=getchar();
	for (;ch<'0'||ch>'9';ch=getchar())	if (ch=='-')	f=-1;
	for (;ch>='0'&&ch<='9';ch=getchar())	x=(x<<1)+(x<<3)+ch-'0';
	return x*f;
}
inline void print(int X){
	if (x<0)	putchar('-'),x=-x;
	if (x>9)	print(x/10);
	putchar(x%10+'0');
}
const int n=1e5;
int pre[(N<<1)+10],now[N+10],child[(N<<1)+10],tot;
int Deep[N+10];
void join(int x,int y){pre[++tot]=now[x],now[x]=tot,child[tot]=y;}
void insert(int x,int y){join(x,y),join(y,X);}
void Dfs(int x,int fa){
	Deep[x]=Deep[fa]+1;
	for (int p=now[x];p;p=pre[p]){
		int son=child[p];
		if (son==fa)	conTinue;
		Dfs(son,X);
	}
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	int n=read(0);
	for (int i=1;i<n;i++){
		int x=read(0),y=read(0);
		insert(x,y);
	}
	Dfs(1,0);
	double Ans=0;
	for (int i=1;i<=n;i++)	Ans+=1.0/Deep[i];
	printf("%.7lfn",Ans);
	return 0;
}

大佬总结

以上是大佬教程为你收集整理的CF280 C. Game on Tree全部内容，希望文章能够帮你解决CF280 C. Game on Tree所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。