시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
7 초 512 MB 2 2 2 100.000%

문제

There is a tree of $N$ vertices numbered $1$ to $N$. A path is a sequence of distinct vertices $(v_1, \ldots, v_k)$ such that $k \geq 1$, $v_i v_{i+1}$ is an edge for all $1 \leq i \leq k-1$, and $v_1 \leq v_k$.

Count the number of paths such that the vertices $v_1, \ldots, v_k$ form a contiguous range, or more formally, the set $\{v_1, \ldots, v_k\} = \{a, a+1, \ldots, b\}$ for some integers $a \leq b$.

입력

The first line contains an integer $N$ ($1 \leq N \leq 50\,000$). The next $N-1$ lines contain the edges of the tree. The $i$-th of these lines contains two space-separated integers $u_i$ and $v_i$ ($1 \leq u_i, v_i \leq N$) denoting that $u_i v_i$ is an edge. It is guaranteed that the given graph is a tree.

출력

On a single line output the desired number of paths.

예제 입력 1

3
1 2
1 3

예제 출력 1

5

힌트

The paths are $(1)$, $(2)$, $(3)$, $(1,2)$, and $(2,1,3)$.