Xenon's Attack on the Gangs
Contest: Codeforces Round 614 (Div. 1)
Difficulty rating: 2300
Tags: combinatorics, dfs and similar, dp, greedy, trees

On another floor of the A.R.C. Markland-N, the young man Simon "Xenon" Jackson, takes a break after finishing his project early (as always). Having a lot of free time, he decides to put on his legendary hacker "X" instinct and fight against the gangs of the cyber world.

His target is a network of $$$n$$$ small gangs. This network contains exactly $$$n - 1$$$ direct links, each of them connecting two gangs together. The links are placed in such a way that every pair of gangs is connected through a sequence of direct links.

By mining data, Xenon figured out that the gangs used a form of cross-encryption to avoid being busted: every link was assigned an integer from $$$0$$$ to $$$n - 2$$$ such that all assigned integers are distinct and every integer was assigned to some link. If an intruder tries to access the encrypted data, they will have to surpass $$$S$$$ password layers, with $$$S$$$ being defined by the following formula:

$$$$$$S = \sum_{1 \leq u < v \leq n} mex(u, v)$$$$$$

Here, $$$mex(u, v)$$$ denotes the smallest non-negative integer that does not appear on any link on the unique simple path from gang $$$u$$$ to gang $$$v$$$.

Xenon doesn't know the way the integers are assigned, but it's not a problem. He decides to let his AI's instances try all the passwords on his behalf, but before that, he needs to know the maximum possible value of $$$S$$$, so that the AIs can be deployed efficiently.

Now, Xenon is out to write the AI scripts, and he is expected to finish them in two hours. Can you find the maximum possible $$$S$$$ before he returns?

Input format:
The first line contains an integer $$$n$$$ ($$$2 \leq n \leq 3000$$$), the number of gangs in the network.

Each of the next $$$n - 1$$$ lines contains integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$; $$$u_i \neq v_i$$$), indicating there's a direct link between gangs $$$u_i$$$ and $$$v_i$$$.

It's guaranteed that links are placed in such a way that each pair of gangs will be connected by exactly one simple path.

Output format:
Print the maximum possible value of $$$S$$$ — the number of password layers in the gangs' network.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
In the first example, one can achieve the maximum $$$S$$$ with the following assignment:

With this assignment, $$$mex(1, 2) = 0$$$, $$$mex(1, 3) = 2$$$ and $$$mex(2, 3) = 1$$$. Therefore, $$$S = 0 + 2 + 1 = 3$$$.

In the second example, one can achieve the maximum $$$S$$$ with the following assignment:

With this assignment, all non-zero mex value are listed below:

- $$$mex(1, 3) = 1$$$
- $$$mex(1, 5) = 2$$$
- $$$mex(2, 3) = 1$$$
- $$$mex(2, 5) = 2$$$
- $$$mex(3, 4) = 1$$$
- $$$mex(4, 5) = 3$$$

Therefore, $$$S = 1 + 2 + 1 + 2 + 1 + 3 = 10$$$.

Example input:
3
1 2
2 3

Example output:
3

Example input:
5
1 2
1 3
1 4
3 5

Example output:
10

Editorial:
The first observation is that, the formula can be rewritten as:
$$$$$$S = \sum_{1 \leq u < v \leq n} mex(u, v) = \sum_{1 \leq x \leq n} \left( \sum_{mex(u, v) = x} x \right) = \sum_{1 \leq x \leq n} \left( \sum_{mex(u, v) \geq x} 1 \right) = \sum_{1 \leq x \leq n} f(x)$$$$$$
Where $$$f(x)$$$ is number of pairs $$$(u, v)$$$ such that $$$1 \leq u < v \leq n$$$ and $$$mex(u, v) \geq x$$$ (in other word, the path from $$$u$$$ to $$$v$$$ contains all numbers from $$$0$$$ to $$$x-1$$$).
Consider the process of placing numbers in order from $$$0$$$ to $$$n-1$$$ (first place number $$$0$$$, then place number $$$1$$$, etc.) on edges of the tree. Suppose that the placement for all numbers from $$$0$$$ to $$$x-1$$$ are fixed, and now we need to place number $$$x$$$. To maximize $$$S$$$, we should try to place $$$x$$$ in a way that there exists a path contain all numbers from $$$0$$$ to $$$x$$$ (if this is possible).
In other word, in the optimal solution, there will be a path connecting two leaf vertices that contain all numbers from $$$0$$$ to $$$l - 1$$$ (where $$$l$$$ is the number of vertices in that path). The placement of numbers from $$$l$$$ to $$$n-2$$$ does not matter, since it will not affect the result.
Now, suppose that the location of such path is fixed, and its length is $$$l$$$. Let $$$a$$$ the sequence of number on edges on the path from $$$u$$$ to $$$v$$$. One can show that, in other to archive maximum $$$S$$$, $$$a$$$ must be a 'valley' sequence (there exist some position $$$p$$$ such that $$$a_1 > a_2 > \ldots > a_p < \ldots < a_{l-1} < a_l$$$.
All the observation above leads to the following dynamic programming solution:
Let $$$dp[u][v]$$$ the maximum value of $$$\sum_{1 \leq x \leq l} f(x)$$$ if all number from $$$0$$$ to $$$l-1$$$ are written on the edges on the path from $$$u$$$ to $$$v$$$ (with $$$l$$$ denote the length of that path). We also define:
• $$$par(r, u)$$$: the parent of vertex $$$u$$$ if we root the tree at vertex $$$r$$$.
• $$$sub(r, u)$$$: the number of vertices in the subtree of vertex $$$u$$$ if we root the tree at vertex $$$r$$$.
The figure below demonstrate $$$par(u, v)$$$ and $$$par(v, u)$$$ for two vertices $$$u$$$ and $$$v$$$ (in the figure, $$$p_{u,v}$$$ is $$$par(u, v)$$$ and $$$p_{v,u}$$$ is $$$par(v, u)$$$).
To calculate $$$dp[u][v]$$$, there are two cases:
• Putting number $$$l$$$ on the edge $$$(u, par(v, u))$$$. In this case:$$$$$$\sum_{1 \leq x \leq l} f(x) = f(l) + \sum_{1 \leq x \leq l-1} f(x) = sub(u, v) \times sub(v, u) + dp[par(v, u)][v]$$$$$$
• Putting number $$$l$$$ on the edge $$$(v, par(u, v))$$$. Similarly, $$$\sum_{1 \leq x \leq l} f(x) = sub(u, v) \times sub(v, u) + dp[u][par(u, v)]$$$
The final formula to calculate $$$dp[u][v]$$$ is:
$$$$$$dp[u][v] = sub(u, v) \times sub(v, u) + \max(dp[par(v, u)][v], dp[u][par(u, v)])$$$$$$
The formula can be calculated in $$$O(1)$$$ if all the values of $$$par(r, u)$$$ and $$$sub(r, u)$$$ are calculated (we can preprocess to calculate these value in $$$\mathcal{O}(n^2)$$$. by doing performing DFS once from each vertex). Therefore, the overall complexity for this algorithm is $$$\mathcal{O}(n^2)$$$.