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)$.