← 返回题目列表

Codeforces · 1060/E

E. 谢尔盖和地铁

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

谢尔盖·谢苗诺维奇(Sergey Semyonovich)是N县市的市长,他曾经日日夜夜地思考如何进一步改善Nkers的生活。对他来说不幸的是,一切都已经完成了,白天他无法再想到任何可能的改进(他现在更喜欢晚上睡觉)。然而,他的助手们找到了解决方案,他们现在在纸上画了一个想象中的城市,并建议市长提出改进建议。

现在他有一张想象中的城市地图,上面有 $$$n$$$ 地铁站。有些车站直接与隧道相连,整个地图就是一棵树(助手时间不够,热情不够)。这意味着每对站之间恰好存在一条简单路径。如果一条路径使用每个隧道不超过一次,我们称该路径为简单路径。

Sergey Semyonovich 最喜欢的质量目标之一是每对站点之间所有成对距离的总和。两个站点之间的距离是它们之间的路径上可能存在的最小隧道数。

Sergey Semyonovich 决定在地铁地图上添加新隧道。特别是,他连接了任意两个没有直接隧道连接但共享公共邻居的站$$$u$$$和$$$v$$$,即存在这样一个站$$$w$$$,原始地图在$$$u$$$和$$$w$$$之间有一条隧道,在$$$w$$$和$$$v$$$之间有一条隧道。您的任务是计算新地图中所有站对之间的成对距离总和。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 200\,000$$$) - 由市长助理绘制的假想城市中的地铁站数量。以下每条 $$$n - 1$$$ 行都包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \ne v_i$$$),这意味着具有这些索引的车站与直接隧道相连。

保证这些$$$n$$$站和$$$n - 1$$$隧道形成一棵树。

输出

在 Sergey Semyonovich 在原始地图中共享公共邻居的所有车站对之间绘制新隧道后,打印一个整数,该整数等于所有车站对之间的距离之和。

示例

输入 #1

4
1 2
1 3
1 4

输出 #1

6

输入 #2

4
1 2
2 3
3 4

输出 #2

7

注意

在第一个示例中,在新地图中,所有站对共享直接连接,因此距离总和为 $$$6$$$。

在第二个示例中,新地图在除 $$$(1, 4)$$$ 之外的所有车站对之间都有一条直接隧道。对于这两个站,距离为 $$$2$$$。