题目描述

给定一棵 $n$ 个结点的树，将树上所有的无向边变成给定方向的有向边，求所有简单路径的长度之和。

有向图中 $a_1$ 到 $a_x$ 的简单路径是形如 $a_1 \rightarrow a_2 \rightarrow a_3\rightarrow \cdots \rightarrow a_x$ 的路径，其中 $a_1,a_2,a_3,\cdots,a_x$ 这 $x$ 个顶点互不相同，其长度为简单路径上的有向边数量。

输入格式

第一行一个整数 $n$，表示树上一共有 $n$ 个结点。

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

输出格式

一个整数，表示有向树上所有简单路径的长度之和。

5
1 2
1 3
1 4
1 5

4

5
1 2
3 1
4 1
5 1

10

4
1 2
2 3
3 4

10

6
1 2
3 2
4 3
5 3
6 3

11

提示

$1 \le n \le 2\times 10^5$，$1\le u, v \le n$，保证输入数据的有向边在看作无向边时，图构成一棵树。