Intervals on Tree
We have a tree with n vertices and n − 1 edges, respectively numbered 1, 2, ..., n and 1, 2, ..., n − 1. Edge i connects vertices u[i] and v[i].
For integers L, R (1 ≤ L ≤ R ≤ n), let us define a function f(L, R) as follows:
Let S be the set of the vertices numbered L through R. f(L, R) represents the number of connected components in the subgraph formed only from the vertex set S and the edges whose endpoints both belong to S.
Compute
Input
The first line contains number n (1 ≤ n ≤ 2 * 10^5). Each of the next n - 1 lines contains two vertices (u[i], v[i]) (1 ≤ u[i], v[i] ≤ n) - an edge in the graph.
Output
Print the value of the sum.
Example
We have six possible pairs (L, R) as follows:
For L = 1, R = 1, S = {1} and we have 1 connected component.
For L = 1, R = 2, S = {1, 2} and we have 2 connected components.
For L = 1, R = 3, S = {1, 2, 3} and we have 1 connected component, since S contains both endpoints of each of the edges 1, 2.
For L = 2, R = 2, S = {2} and we have 1 connected component.
For L = 2, R = 3, S = {2, 3} and we have 1 connected component, since S contains both endpoints of Edge 2.
For L = 3, R = 3, S = {3} and we have 1 connected component.
The sum of these is 7.