M - Tree and Intervals Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

問題文

N 頂点の木があり、頂点は 1, \dots, N と、辺は 1, \dots, N-1 と番号付けられています。辺 i \, (1 \leq i \leq N - 1) は頂点 U_i, V_i を結んでいます。

1 \leq l \leq r \leq N - 1 を満たす全ての整数組 (l, r) に対する以下の値の総和を求めてください。

  • 頂点 1 から出発し、番号が l 以上 r 以下である辺のみを 0 本以上辿って到達することができる頂点の個数。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq U_i \lt V_i \leq N \, (1 \leq i \leq N - 1)
  • 与えられるグラフは木
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N
U_1 V_1
\vdots
U_{N - 1} V_{N - 1}

出力

答えを出力せよ。

入力例 1

5
2 3
1 2
2 4
3 5

出力例 1

24

たとえば、(l, r) = (2, 4) のとき、頂点 1 から到達することができるのは頂点 1, 2, 4 であり、(l, r) = (3, 3) のとき、頂点 1 から到達することができるのは頂点 1 のみです。

入力例 2

2
1 2

出力例 2

2

入力例 3

7
1 2
2 7
4 6
3 6
4 5
1 5

出力例 3

49

Problem Statement

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.

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.

Input

The input is given from Standard Input in the following format:

N
U_1 V_1
\vdots
U_{N - 1} V_{N - 1}

Output

Print the answer.

Sample Input 1

5
2 3
1 2
2 4
3 5

Sample Output 1

24

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.

Sample Input 2

2
1 2

Sample Output 2

2

Sample Input 3

7
1 2
2 7
4 6
3 6
4 5
1 5

Sample Output 3

49