P3978 [TJOI2015] Probability Theory

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 a positive integer $n$, the number of nodes in the rooted tree.

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

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