A8926. Game on Tree

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

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$