Problem 872

Recursive Tree

A sequence of rooted trees $T_n$ is constructed such that $T_n$ has $n$ nodes numbered $1$ to $n$.

The sequence starts at $T_1$, a tree with a single node as a root with the number $1$.

For $n > 1$, $T_n$ is constructed from $T_{n-1}$ using the following procedure:

Trace a path from the root of $T_{n-1}$ to a leaf by following the largest-numbered child at each node.
Remove all edges along the traced path, disconnecting all nodes along it from their parents.
Connect all orphaned nodes directly to a new node numbered $n$, which becomes the root of $T_n$.

For example, the following figure shows $T_6$ and $T_7$. The path traced through $T_6$ during the construction of $T_7$ is coloured red.

Let $f(n, k)$ be the sum of the node numbers along the path connecting the root of $T_n$ to the node $k$, including the root and the node $k$. For example, $f(6, 1) = 6 + 5 + 1 = 12$ and $f(10, 3) = 29$.

Find $f(10^{17}, 9^{17})$.

递归树

递归构造一个有根树序列$T_n$，其中$T_n$有$n$个节点，编号分别为$1$至$n$。

序列的第一项为$T_1$，这棵树只包含一个编号为$1$的节点作为根节点。

对于$n>1$，树$T_n$根据下列规则由$T_{n-1}$构造而成：

从$T_{n-1}$的根节点出发，不断沿编号最大的子节点移动，直至到达叶节点，并记录相应的路径。
移除路径上的所有边，使路径上的节点与其父节点分离。
将所有被分离出的节点连接到一个新的、编号为$n$的节点，并将其作为$T_n$的根节点。

例如，下图展示了$T_6$和$T_7$。$T_6$中用于构造$T_7$的路径被标示为红色。

记$f(n, k)$为$T_n$中连接根节点和编号为$k$的节点的路径上，所有节点（包括路径的两端）的编号和。例如，$f(6, 1) = 6 + 5 + 1 = 12$，$f(10, 3) = 29$。

求$f(10^{17}, 9^{17})$。