PKU Online Judge 1055:Tree

在信息学竞赛中，我们经常要遇到树这种结构。

一棵树中除根结点外有且仅有一个父亲，而可能有很多儿子。所以，当我们要生成一棵树的时候，我们通常使用以下算法：



对树中的每个点定义一个深度。第 1 个节点的深度为 1，第 i 个点的深度就是 Father_i的深度加 1 。

有一天，Picks突然对这个算法产生了强烈的兴趣，他想知道，在随机函数完全公平的情况下，给出树的节点数最大值的限制 N ，从所得的树上任选一个节点，其深度的期望是多少？

数据范围

评测方式

对于每个测试点，你给出的答案需满足以下不等式才能获得该测试点的分数。

1
2

1.0000000000
1.2500000000

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
using namespace std;
#define M 2000000
double pri[M];
int main()
{int i;for(pri[0]=0,i=1;i<M;i++){pri[i]=pri[i-1]+1.0/i;}double temp,la=pri[M-1]-log(1.0*M);long long n;while(scanf("%lld",&n)!=EOF){if(n<M)temp=pri[n];else temp=log(1.0*(n+1))+la;printf("%.10f\n",temp*(n+1)/n-1.0);}return 0;
}