P2274 [HNOI2002] Ordering of Binary Trees

1. The empty tree is numbered $0$, and the tree with only the root node is numbered $1$. 2. Let $m$ be any non-negative integer. Then the number of any tree with $m$ nodes is smaller than the number of any tree with $m+1$ nodes. 3. Let $A, B$ be two trees with the same number of nodes (with $A \ne B$). The number of $A$ is smaller than that of $B$ if and only if one of the following holds: 1. The number of the left subtree of $A$ is smaller than the number of the left subtree of $B$. 2. The numbers of the left subtrees of $A$ and $B$ are equal (that is, the left subtrees of $A$ and $B$ have the same shape), and the number of the right subtree of $A$ is smaller than the number of the right subtree of $B$. 4. Following the usual rule, the numbers are consecutive non-negative integers. Each tree corresponds to a unique number, and each non-negative integer corresponds to a unique tree. (Note: all trees mentioned above are binary trees.)

A single line with an integer $n$, $1\le n\le 500{,}000{,}000$. For $10\%$ of the testdata, the number of nodes in the tree does not exceed three.

A single line: the binary tree corresponding to number $n$. Output as follows: - If it is a one-node binary tree, output $X$. - If the left and right subtrees are $L$ and $R$, and their respective outputs are $L'$ and $R'$, then output $\texttt{(}L'\texttt{)}X\texttt{(}R'\texttt{)}$; when the left subtree is empty, output $X\texttt{(}R'\texttt{)}$; when the right subtree is empty, output $\texttt{(}L'\texttt{)}X$.

Translated by ChatGPT 5