g6-07654. 地铁·两跳距离和 未做

改编自 Codeforces 1060E（题面重写、数据自造；原题 URL：https://codeforces.com/problemset/problem/1060/E）

给定一棵 $n$ 个结点的树。在原有边上，额外连接所有距离为 2 的点对（新边长度视为 $1$）。求新图中所有点对最短路长度之和。可以证明新距离 = $\lceil$ 原距离 $/2\rceil$。

输入格式：第一行 $n$；接下来 $n-1$ 行 $u,v$。

输入：

3
1 2
2 3

输出：

3

原距离 $1,1,2$ → 新距离 $1,1,1$，和 $3$？注意 $(1,2)$ 原距 $1$ 新距 $1$；$(2,3)$ $1$；$(1,3)$ 原 $2$ 新 $1$ → 和 $3$。以程序为准。

数据范围：$1\le n\le 2\times 10^5$。