CF1179D.Fedor Runs for President

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.

费多尔正在竞选比特兰（Byteland）总统！在辩论中，他将被问及如何解决比特兰的交通问题。这是一个非常棘手的问题，因为比特兰当前的交通系统是一棵树（即一个无环的连通图）。费多尔的团队从比特兰交通部获悉：预算中仅够修建一条额外的道路。在辩论中，他打算宣称：将修建这条道路，以使全国范围内不同的简单路径数量最大化。其中，简单路径指每顶点至多经过一次的路径；若两条简单路径所含边集不同，则称它们是不同的。

但比特兰的科学水平已严重衰退，因此费多尔的团队未能找到任何科学家来回答：在交通系统中恰好添加一条边后，最多能有多少条不同的简单路径？

请帮助费多尔解决该问题。

允许在已连通的两个顶点之间添加边，但不允许添加自环边。

本题中，我们只考虑长度至少为 2 的简单路径。

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.

第一行包含一个整数 $n$（$2 \leq n \leq 500\ 000$）—— 表示比特兰交通系统中的顶点数量。

接下来的 $n - 1$ 行，每行包含两个整数 $v_i$ 和 $u_i$（$1 \leq v_i, u_i \leq n$）。保证该图是一棵树。

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

输出一个整数——即添加一条边后所能达到的简单路径的最大数量。