CF1060E Sergey and Subway

谢尔盖·谢苗诺维奇是某县级市 N 的市长，他总是日夜思考如何进一步改善 N 市市民的生活。不幸的是，他能想到的所有改进措施都已经实施过了，白天再也想不出新的改进方案（现在他更喜欢晚上睡觉）。不过，他的助手们找到了一个解决办法：他们在纸上画出一座虚构的城市，并建议市长为这座城市提出改进建议。 现在，他手上有一张虚构城市的地铁站分布图，共有 $n$ 个地铁站。有些地铁站之间通过隧道直接相连，并且整个地图构成一棵树（助手们缺乏时间和热情）。这意味着每一对地铁站之间恰好存在一条简单路径。我们称一条路径为简单路径，如果它经过每条隧道的次数不超过一次。 谢尔盖·谢苗诺维奇最喜欢的一个质量目标是所有地铁站两两之间距离之和。两站之间的距离定义为它们之间路径上最少需要经过的隧道数。 谢尔盖·谢苗诺维奇决定在地铁图上新增隧道。具体来说，他将所有原本没有直接隧道连接、但有一个共同邻居的两座地铁站 $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$），表示编号为 $u_i$ 和 $v_i$ 的地铁站之间有一条直接隧道。 保证这 $n$ 个地铁站和 $n-1$ 条隧道构成一棵树。

输出一个整数，表示在为所有有共同邻居的地铁站对新建隧道后，所有地铁站两两之间距离之和。

在第一个样例中，新图中所有地铁站对之间都有直接连接，因此距离之和为 $6$。 在第二个样例中，新图中除了地铁站对 $(1, 4)$ 外，其余所有地铁站对之间都有直接隧道。对于这两个地铁站，它们之间的距离为 $2$。 由 ChatGPT 4.1 翻译