CF1179D Fedor Runs for President

费多尔正在竞选 Byteland 的总统！在辩论中，他将被问及如何解决 Byteland 的交通问题。这是一个非常棘手的问题，因为 Byteland 的交通系统目前是一棵树（即一个无环连通图）。费多尔的团队从 Byteland 交通部了解到，预算中只够修建一条额外的道路。在辩论中，他打算说他会修建这条道路，以最大化全国不同简单路径的数量。简单路径是指每个顶点最多经过一次的路径。如果两条简单路径的边集不同，则认为它们是不同的。 但 Byteland 的科学水平正在衰退，所以费多尔的团队没能找到科学家来回答：在交通系统上恰好添加一条边后，最多可以获得多少条不同的简单路径？ 请你帮助费多尔解决这个问题。 可以在已经连通的顶点之间添加一条边，但不能自环。 在本题中，我们只考虑长度至少为 $2$ 的简单路径。

第一行包含一个整数 $n$（$2 \leq n \leq 500\,000$），表示 Byteland 交通系统中的顶点数。 接下来的 $n-1$ 行，每行包含两个整数 $v_i$ 和 $u_i$（$1 \leq v_i, u_i \leq n$）。保证给定的图是一棵树。

输出一个整数，表示添加一条边后最多可以获得的不同简单路径数量。

由 ChatGPT 4.1 翻译