Diameter of a Composite Tree

We are given a tree (T) with (n) nodes, where the nodes are numbered from (1) to (n) and (1) is the root. For each (i) with (2 \le i \le n), you are given an integer (f_i) which is the parent of node (i) in (T). We call (T) the unit tree.

We then form a new tree (G) with (n^2) nodes by taking (n) copies of (T), and connecting them using (n-1) extra edges as follows:

1. Place the \(n\) copies of \(T\) and label them from \(1\) to \(n\). In the copy with label \(a\), denote the nodes as \((a,1)\), \((a,2)\), …, \((a,n)\) corresponding to the nodes of \(T\).
2. For every \(i\) with \(2 \le i \le n\), add an edge connecting node \((i,1)\) in the \(i\th copy and node \((f_i, f_i)\) in the \(f_i\)th copy. (Recall that in \(T\), \(f_i\) is the parent of \(i\).)

This construction results in a tree (G) with (n^2) nodes. Your task is to compute the maximum number of nodes on a simple path in (G) (i.e. the diameter measured by the number of nodes).

A key observation is that the extra edges connect the copies following the structure of (T) itself. In each copy, we can take a path wholly contained in a copy (with length equal to the diameter of (T)), or a path that goes from one copy to another.

Define the following quantities for the unit tree (T) (where distances are measured in the number of edges):

• Let \(d_T\) be the diameter of \(T\) (i.e. the maximum distance between any two nodes in \(T\)). The diameter within one copy then contains \(d_T + 1\) nodes.
• Let \(L\) be the maximum distance from the root \(1\) to any other node in \(T\) (i.e. the height of the tree).

For paths that cross copies, the structure forces you to exit a copy from the node ((i,i)) (corresponding to the node with the same label as its copy number) and enter the other copy through ((j,1)). A detailed analysis shows that the overall diameter of (G) (in terms of number of nodes) is given by

[ \text{answer} = \max\Big{d_T + 1,; 2d_T + L + 1\Big}. ]

Your task is to compute and output this number given the input tree (T).

Input Format:

• The first line contains a single integer \(n\) (\(1 \le n \le 10^5\)).
• If \(n \ge 2\), the second line contains \(n-1\) integers: \(f_2, f_3, \dots, f_n\) where \(1 \le f_i < i\), representing the parent of node \(i\) in \(T\).

Output Format:

• Output a single integer: the maximum number of nodes on a simple path in the constructed tree \(G\).

Example:

Input:

2
1

Explanation: In this case, (T) has 2 nodes with edge between 1 and 2. The constructed tree (G) consists of 2 copies of (T) and one extra connecting edge between ((2,1)) and ((1,1)). The longest path is (2,2) - (2,1) - (1,1) - (1,2) with 4 nodes.

Output:

4

inputFormat

The input begins with an integer n (the number of nodes in the unit tree). If n > 1, the next line contains n-1 integers: f2, f3, ..., fn where fi (1 ≤ fi < i) is the parent of node i in the unit tree T.

outputFormat

Output a single integer — the maximum number of nodes on a simple path (i.e. the diameter in terms of nodes) of the constructed tree.

sample

1

1