P10794 [SpOI - R1] A Drum Set Can Stand C

You are given a tree with $n$ nodes, where the root is node $1$. You can perform the following **“Stand C operation”** any number of times. In one **“Stand C operation”**: Choose a leaf node $x$ in the tree, then choose an edge on the path from the root to $x$ and delete it; after that, add an edge connecting $x$ and the root. You need to find the maximum possible diameter of the tree after performing some number of **“Stand C operations”**. **Note: A leaf node is defined as a node that is not the root and has degree $1$.**

**This problem contains multiple test cases.** The first line contains an integer $T$, the number of test cases. Then follow $T$ test cases. For each test case, the first line contains an integer $n$. The second line contains a sequence $f_i$ of length $n-1$, where the $i$-th value is the parent of node $i+1$ in the tree.

For each test case, output one integer per line, the answer.

### Explanation of Sample #1 If no operation is performed, the diameter of the tree is $2$. It can be proven that this is the maximum diameter. ### Explanation of Sample #2 The tree in the sample is as follows:  Only one “Stand C operation” is needed: choose leaf node $6$, disconnect the edge from $1$ to $4$, then connect $6$ and $1$. This will make the tree become a chain, with diameter $6$. It can be proven that this is the maximum diameter. ### Constraints **Please pay attention to how constant factors affect program efficiency.** **This problem enables subtask bundling and subtask dependencies.** For all testdata, $1\leq T\leq 10^4$, $2 \leq n \leq 2\times 10^5$, and the input is guaranteed to form a tree. | Subtask | $T\leq$ | $n\leq$ | Special property | Score | Dependency | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | 1 | $10^4$ | $10$ | None | $15$ | None | | 2 | $10^4$ | $20$ | None | $15$ | 1 | | 3 | $10^4$ | $90$ | None | $20$ | 1,2 | | 4 | $10^4$ | $2\times 10^5$ | $A$ | $15$ | None | | 5 | $15$ | $2\times 10^5$ | None | $35$ | 1,2,3,4 | **In particular, for Subtask 4, it is guaranteed that $\sum n\leq 3\times 10^6$.** Special property $A$: There does not exist a pair $(x,y)$ with $x\neq 1\land y\neq 1$ such that $\text{LCA}(x,y)=1$. Translated by ChatGPT 5