题目描述

给定一棵 $n$ 个节点的树，有 $n-1$ 条边。对于每条边，将其断开后树分裂为两个部分，设两部分节点数分别为 $w_1$ 与 $w_2$，该边的贡献为 $|w_1-w_2|$。求所有边的贡献之和。

输入格式

第一行一个整数 $n$。

接下来 $n-1$ 行，每行两个整数 $u,v$，表示一条边。

输出格式

一行一个整数，表示答案。

5
1 2
1 3
2 4
2 5

10

3
1 2
2 3

2

样例解释

样例 $1$：以 $1$ 为根。边 $(1,2)$ 断开后子树 $\{2,4,5\}$ 有 $3$ 个节点，余部 $2$ 个，贡献 $|3-2|=1$。边 $(1,3)$：$|1-4|=3$。边 $(2,4)$：$|1-4|=3$。边 $(2,5)$：$|1-4|=3$。总 $1+3+3+3=10$。

样例 $2$：链状。边 $(1,2)$：$|1-2|=1$。边 $(2,3)$：$|1-2|=1$。总 $2$。

数据范围与约定

下发样例

下发样例下载