D. 费奥多尔竞选总统
每次测试的时间限制：2 秒
每次测试的内存限制：256 兆字节

费奥多尔正在竞选比特兰的总统！在辩论中，他将被问及如何解决比特兰的交通问题。这是一个非常困难的问题，因为比特兰的交通系统目前是一棵树（无环连通图）。费奥多尔的团队在比特兰交通部发现，预算中只够修建一条额外的道路。在辩论中，他将表示，他会修建这条道路，以最大化国家中不同简单路径的数量。简单路径是指不重复经过任何顶点的路径。如果两条路径的边集合不同，则称它们不同。

但比特兰的科学发展已经衰退，费奥多尔的团队未能找到任何科学家来回答：在交通系统中恰好添加一条边后，他们可以获得多少条不同的简单路径？

帮助费奥多尔解决这个问题。

可以在已经连通的顶点之间添加一条边，但不能是自环。

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

输入
第一行包含一个整数 $n$（$2 \le n \le 500\,000$）—— 比特兰交通系统中的顶点数。

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

输出
输出一个整数 —— 添加一条边后可以得到的最大简单路径数量。

示例

示例 1
输入

2
1 2

输出

2

示例 2
输入

4
1 2
1 3
1 4

输出

11

示例 3
输入

6
1 2
1 3
3 4
3 5
4 6

输出

29