Description

To boost her IQ, ZJY started studying probability theory. One day, she came up with this question: among all non-isomorphic rooted binary trees with $n$ nodes, chosen uniformly at random, what is the expected number of leaf nodes?

The pseudocode to check whether two trees are isomorphic is as follows:

$$\def\arraystretch{1.2} \begin{array}{ll} \hline \textbf{Algorithm 1}&\text{Check}(T1,T2) \\ \hline 1&\textbf{Require: }\text{ nodes }T1,T2\text{ of the two trees}\\ 2&\qquad\textbf{if}\ \ T1=\text{null}\textbf{ or }T2=\text{null}\textbf{ then }\\ 3&\qquad\qquad\textbf{return}\ \ T1=\text{null}\textbf{ and }T2=\text{null}\\ 4&\qquad\textbf{else}\\ 5&\qquad\qquad\textbf{return}\ \text{Check}(T1\to\mathit{leftson},T2\to\mathit{leftson}) \\ & \qquad\qquad\qquad \textbf{ and }\text{Check}(T1\to\mathit{rightson},T2\to\mathit{rightson})\\ 6&\qquad\textbf{endif}\\ \hline \end{array}$$

Input Format

Input a positive integer $n$, the number of nodes in the rooted tree.

Output Format

Output the expected number of leaf nodes of the tree. The error must be less than $10^{-9}$.

1

1.000000000

3

1.200000000

Hint

Constraints

• For $30\%$ of the testdata, $1 \le n \le 10$.
• For $70\%$ of the testdata, $1 \le n \le 100$.
• For $100\%$ of the testdata, $1 \le n \le 10^9$.

Translated by ChatGPT 5