시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
7 초 | 512 MB | 22 | 10 | 10 | 47.619% |
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.
3 1 2 1 3
5
The paths are $(1)$, $(2)$, $(3)$, $(1,2)$, and $(2,1,3)$.