19340번 - Tree Paths 다국어

문제

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.

제한

힌트

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