3690. [CF1060E]Sergey and Subway

【题目描述】

给出一颗 $N$ 个节点的树，现在我们在原图中每个不直接连边但是中间只间隔一个点的两个点之间连一条边。

比如在原图中 $u$ 与 $v$ 连边，$v$ 与 $w$ 连边，但是 $u$ 与 $w$ 不连边，这时候我们就需要连一条 $u$ 与 $w$ 的边。

现在我们需要求出新图中每一个点对 $(i,j)\ (1 \le i \le j \le N)$ 的经过的最少的边数和。

【输入格式】

第一行包含一个整数 $N$，表示树的节点数量。

接下来 $N-1$ 行，每行两个整数 $x,y$，表示节点 $x,y$ 之间有一条边。

【输出格式】

一个整数，表示所有点对之间的最少边数之和。

【样例输入1】

4
1 2
1 3
1 4

【样例输出1】

6

【样例输入2】

4
1 2
2 3
3 4

【样例输出2】

7

【样例说明】

第一组样例中没有新边，不做解释。

第二组样例中，建出新边后，得到：

$(1,2)$ 之间最少 $1$ 条边，$(1,3)$ 之间最少 $1$ 条边，$(1,4)$ 之间最少 $2$ 条边（即 $1\to 3,3 \to 4$）。

$(2,3)$ 之间最少 $1$ 条边，$(2,4)$ 之间最少 $1$ 条边。

$(3,4)$ 之间最少 $1$ 条边。

故答案为 $1+1+2+1+1+1=7$。

【数据规模与约定】

对于 30% 的数据，$1 \le n \le 10^3$。

对于 100% 的数据，$1 \le n \le 2 \times 10^5$。

【来源】

Codeforces Round #513 by Barcelona Bootcamp (rated, Div. 1 + Div. 2)