TreeDiameters

This problem is about undirected trees with unit-length edges. In such a tree, the distance between two vertices x and y is the number of edges on the unique simple path that connects x and y.

Given a tree T, we can compute the distances between all pairs of its vertices. The largest of all those distances is called the diameter of the tree.

In a tree T, an unordered pair {x, y} of vertices is called an antipodal pair if their distance is equal to the diameter of the tree.

The value A(T) is defined as the number of distinct antipodal pairs in the tree T. Note that {a, b} is the same pair of vertices as {b, a}.

A subgraph of a graph G is a graph that can be obtained from G by erasing some (possibly none) vertices and some (possibly none) edges. A subtree of a tree T is a subgraph of T that is a tree. In other words, the subtrees of a tree T are precisely all connected subgraphs of T. Note that T is considered to be its own subtree.

You are given a int[] p with n elements. This int[] describes a tree T with n+1 vertices. The vertices are numbered 0 through n. For each valid i, there is an edge between the vertices p[i] and (i+1).

Consider all possible subtrees of the given tree T. For each such subtree T' that has at least two vertices, determine the value A(T'): the number of antipodal pairs in T'. Return the largest of all those values.

In other words, among all possible subtrees of the given tree T find the one that has the most antipodal pairs, and return their count.

Note that when counting antipodal pairs in a subtree we are looking for pairs of vertices with distance equal to the diameter of that particular subtree (which may be smaller than the diameter of the original tree).