Fedor Runs for President
Contest: Codeforces Round 569 (Div. 1)
Difficulty rating: 2700
Tags: data structures, dp, trees

Fedor runs for president of Byteland! In the debates, he will be asked how to solve Byteland's transport problem. It's a really hard problem because of Byteland's transport system is now a tree (connected graph without cycles). Fedor's team has found out in the ministry of transport of Byteland that there is money in the budget only for one additional road. In the debates, he is going to say that he will build this road as a way to maximize the number of distinct simple paths in the country. A simple path is a path which goes through every vertex no more than once. Two simple paths are named distinct if sets of their edges are distinct.

But Byteland's science is deteriorated, so Fedor's team hasn't succeeded to find any scientists to answer how many distinct simple paths they can achieve after adding exactly one edge on the transport system?

Help Fedor to solve it.

An edge can be added between vertices that are already connected, but it can't be a loop.

In this problem, we consider only simple paths of length at least two.

Input format:
The first line contains one integer $$$n$$$ ($$$2 \leq n \leq 500\ 000$$$) — number of vertices in Byteland's transport system.

Each of the following $$$n - 1$$$ lines contains two integers $$$v_i$$$ and $$$u_i$$$ ($$$1 \leq v_i, u_i \leq n$$$). It's guaranteed that the graph is tree.

Output format:
Print exactly one integer — a maximal number of simple paths that can be achieved after adding one edge.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
2
1 2

Example output:
2

Example input:
4
1 2
1 3
1 4

Example output:
11

Editorial:
We suppose we add an edge $$$u-v$$$. Path $$$u-v$$$ in the tree contains vertices $$$t_1, \ldots, t_k$$$, where $$$k$$$ — length of the path, $$$t_1 = u, t_k = v$$$. For each vertex $$$x$$$ of the tree, we say that $$$f(x)$$$ — the closest to $$$x$$$ vertex of this path. Finally, we call a component of $$$t_i$$$ all vertices $$$x$$$ having $$$f(x) = t_i$$$.
One can notice that after adding an edge every pair of vertices may generate not more than two simple paths — the first one had already been in the tree, the second one may be generated using added edge. One can notice that every new path is generated by every pair of vertices lying in different components. Let's consider the sizes of components — $$$s_1, \ldots, s_k$$$ respectively. So new path isn't generated for $$$\sum\limits_{i=1}^k \frac{s_i \cdot (s_i - 1)}{2}$$$ pairs of vertices. So we have the following problem — to minimize this sum.
Thus, we should minimize $$$\sum\limits_{i=1}^k \frac{s_i \cdot (s_i - 1)}{2}$$$, what is the same as, $$$\sum\limits_{i=1}^k s_i \cdot (s_i - 1)$$$ = $$$\sum\limits_{i=1}^k s_i \cdot s_i - s_i$$$ = $$$\sum\limits_{i=1}^k s_i^{2}$$$ (because of $$$\sum\limits_{i=1}^k s_i$$$ = $$$n$$$).
It's obvious now that $$$u, v$$$ are leafs of the tree (else we could decrease this sum increasing the path).
For convenience, we will hang the tree for a non-leaf. We will consider that $$$t_l = lca(u, v)$$$ in the path. Then, the desired sum will be:
$$$A + B + C$$$, где
$$$A = sz_{t_1}^{2} + (sz_{t_2} - sz_{t_1})^{2} + \ldots + (sz_{t_l} - sz_{t_{l-1}})^{2}$$$
$$$B = (n - sz_{t_{l-1}} - sz_{t_{l+1}})^{2}$$$
$$$C = sz_{t_k}^{2} + (sz_{t_{k-1}} - sz_{t_k})^{2} + \ldots + (sz_{t_l} - sz_{t_{l+1}})^{2}$$$
When we fix $$$L = t_l$$$, $$$p_1 = t_{l+1}$$$ и $$$p_2 = t_{l-1}$$$, one can realize that $$$A$$$ doesn't depend on $$$L$$$ at all but depends on the subtree of $$$p_1$$$, as $$$C$$$ depends of the subtree of $$$p_2$$$. Thus these sums can easily be calculated using $$$DP$$$. Let $$$dp[x]$$$ be that optimal sum for vertex $$$x$$$. Then, when we fix $$$L$$$ — $$$lca(u, v)$$$ — we need to calculate the minimum by all different $$$p_1, p_2$$$ — children of $$$L$$$ — the following sum:
$$$dp[p_1] + dp[p_2] + (n - sz_{p_1} - sz_{p_2})^{2}$$$.
We get:
$$$n^{2} + dp[p1] - 2 \cdot n \cdot sz_{p_1} + dp[p2] - 2 \cdot n \cdot sz_{p_2} + 2 \cdot sz_{p_1} \cdot sz_{p_2}$$$.
Now one can see that if we sort all vertices by $$$sz$$$ in non-increasing order one can use Convex Hull Trick — for the next vertex $$$p_2$$$ we find minimum by all $$$p_1$$$ which are already processed by functions $$$2 \cdot sz_{p_1} \cdot sz_{p_2} - 2 \cdot n \cdot sz_{p_1} + dp[p1]$$$, i.e $$$k = 2 \cdot sz_{p_1}$$$, $$$b = - 2 \cdot n \cdot sz_{p_1} + dp[p1]$$$. $$$k$$$ decreases, thus we write usual CHT.
Complexity is $$$O(n \cdot log(n))$$$.