AT_past202212_m 木と区間

There is a tree with $ N $ vertices, whose vertices are numbered $ 1, \dots, N $ and edges are numbered $ 1, \dots, N-1 $ . Edge $ i \, (1 \leq i \leq N - 1) $ connects vertices $ U_i $ and $ V_i $ . Find the sum of the following value over all integer pairs $ (l, r) $ such that $ 1 \leq l \leq r \leq N - 1 $ : - the number of vertices that are reachable from vertex $ 1 $ using zero or more edges numbered between $ l $ and $ r $ , inclusive.

The input is given from Standard Input in the following format: > $ N $ $ U_1 $ $ V_1 $ $ \vdots $ $ U_{N - 1} $ $ V_{N - 1} $

Print the answer.

### Sample Explanation 1 For example, if $ (l, r) = (2, 4) $ , one can get from vertex $ 1 $ to vertices $ 1 $ , $ 2 $ , and $ 4 $ ; if $ (l, r) = (3, 3) $ , one can get from vertex $ 1 $ to just vertex $ 1 $ . ### Constraints - $ 2 \leq N \leq 2 \times 10^5 $ - $ 1 \leq U_i \lt V_i \leq N \, (1 \leq i \leq N - 1) $ - The given graph is a tree. - All values in the input are integers.