← 返回题目列表

Codeforces · 1179/D

D. 费多尔竞选总统

中文机器翻译题面 查看原题

Fedor 竞选 Byteland 总裁!在辩论中,他会被问到如何解决Byteland的交通问题。这是一个非常困难的问题,因为 Byteland 的运输系统现在是一棵树(没有循环的连通图)。 Fedor 的团队在 Byteland 交通部发现,预算中只有额外一条道路的资金。在辩论中,他将表示,他将修建这条道路,以最大限度地增加该国独特的简单道路的数量。简单路径是经过每个顶点不超过一次的路径。如果两条简单路径的边集不同,则它们被命名为不同的。

但是 Byteland 的科学已经恶化,所以 Fedor 的团队还没有成功找到任何科学家来回答在运输系统上添加一个边缘后他们可以实现多少条不同的简单路径?

帮助Fedor解决它。

可以在已连接的顶点之间添加边,但不能是环。

在这个问题中,我们仅考虑长度至少为 2 的简单路径。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 500\ 000$$$) — Byteland 传输系统中的顶点数。

以下 $$$n - 1$$$ 行中的每一行都包含两个整数 $$$v_i$$$ 和 $$$u_i$$$ ($$$1 \leq v_i, u_i \leq n$$$)。保证图是树。

输出

精确打印一个整数——添加一条边后可以实现的最大简单路径数。

示例

输入 #1

2
1 2

输出 #1

2

输入 #2

4
1 2
1 3
1 4

输出 #2

11

输入 #3

6
1 2
1 3
3 4
3 5
4 6

输出 #3

29