Game on Tree

**题目描述** 给定一棵有根树，结点编号从 $1$ 到 $n$。根结点为 $1$ 号结点。 对于每一次操作，等概率的选择一个**尚未被删去**的结点并将它及其子树全部删去。当所有结点被删除之后，游戏结束；也就是说，删除 $1$ 号结点后游戏即结束。 要求求出删除所有结点的期望操作次数。 **输入格式** 第一行，一个正整数 $n$ 表示结点数量。 接下来 $n-1$ 行每行两个数，表示树上的一条连接 $a_i$ 与 $b_i$ 的边 $(a_i,b_i)$ 保证给定的数据是一棵树。 **输出格式** 输出一个实数，表示期望操作次数。答案误差在 $10^{-6}$ 之内则认为正确。 **样例解释** 在第一个样例中，有两种情况： 一种是直接删除根（即 $1$ 号结点），另一种是先删去 $2$ 号结点，再删除 $1$ 号结点。 操作次数的期望是 $1\times \dfrac12+2\times\dfrac12=1.5$。 在第二个样例中，情况更为复杂。其中有两种情况会将问题转化成第一个样例，而剩下的一种情况会一次全部删除。 操作次数的期望是 $1\times\dfrac13+(1+1.5)\times\dfrac23=\dfrac13+\dfrac53=2$。

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.

The first line contains integer $ n $ $ (1<=n<=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<=a_{i},b_{i}<=n; a_{i}≠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.

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} $ .

2
1 2

1.50000000000000000000

3
1 2
1 3

2.00000000000000000000

In the first sample, there are two cases. One is directly remove the root and another is remove the root after one step. Thus the expected steps are: $ 1×(1/2)+2×(1/2)=1.5 $ In the second sample, things get more complex. There are two cases that reduce to the first sample, and one case cleaned at once. Thus the expected steps are: $ 1×(1/3)+(1+1.5)×(2/3)=(1/3)+(5/3)=2 $