P7238 Lost Forest.

First, you are given a tree with $n$ nodes rooted at $1$, called the “unit tree”. Now there are $n$ trees with exactly the same structure as the “unit tree”. You need to connect these $n$ trees together using $n - 1$ edges. For convenience, use the notation $(a,b)$ to represent: in the tree represented by node $a$, the node whose label is $b$. The connection method is as follows: 1. Arrange the $n$ trees according to the structure of the “unit tree”. 2. For each $i(1

The first line contains a positive integer $n$, the number of nodes in the “unit tree”. The next $n - 1$ lines each contain two positive integers $u,v$, representing an edge in the “unit tree”.

Output one line with a positive integer, the maximum number of **nodes** on a simple path between two nodes in the tree.

#### Sample Explanation Sample #1  Sample #2: As shown in the figure below, the path with endpoints $(3,4)$ and $(4,4)$ contains $9$ nodes, and its length is $9$.  Sample #3: As shown in the figure below, choose $(6,6)$ and $(9,9)$, and it contains $11$ nodes.  In fact, for any two orange nodes whose lowest common ancestor is $1$, the answer is always $11$. #### Constraints **This problem uses bundled testdata.** | Subtask ID | Score | $n\le$ | Special Property | | :----------: | :----------: | :----------: | :----------: | | $1$ | $10$ | $10$ | $\times$ | | $2$ | $12$ | $10^6$ | $v=u+1$ | | $3$ | $6$ | $10^6$ | $u=1$ | | $4$ | $18$ | $=2^k(k\in\mathbf{Z})$ | $u=\left\lfloor\dfrac{v}{2}\right\rfloor$ | | $5$ | $27$ | $10^3$ | The shape of the tree is random. | | $6$ | $27$ | $10^6$ | $\times$ | For $100\%$ of the testdata: $1\leq n\leq10^6$, and node labels are between $1$ and $n$. **This problem may be slightly tight on constants.** The time limit has been reduced to $1\text{s}$ for the following reasons: - The discussion board believes this problem is the same as an existing one. To prevent the so-called “enhanced version” $O(n\log n)$ solution from directly passing this problem, the time limit was reduced. - The optimal solution can run within $200\text{ms}$. - Because the author is lazy and did not want to change $n\le10^6\rightarrow n\le10^7$, they can only reduce the time limit to block the so-called original-problem solution (which is actually incorrect). Translated by ChatGPT 5