F - Sum of Mex 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 525 点

問題文

N 頂点の木 T が与えられます。各頂点には 0 から N-1 までの番号がついており、 i 番目 (1\le i\le N-1) の辺は頂点 u_i と頂点 v_i を双方向に繋いでいます。（頂点番号は 0-indexed で辺番号が 1-indexed であることに注意してください。）

0 以上 N 未満の整数の組 (i,j) に対し f(i,j) を以下のように定めます：

  • 木 T の頂点 i から頂点 j までのパスに 含まれない 頂点のうち番号が最も小さい頂点の頂点番号。
    • ただし、頂点 i から頂点 j までのパスに頂点 0 から頂点 N-1 まで全ての頂点が含まれる場合 f(i,j)=N とする。

木 T の頂点 i から頂点 j までのパスに頂点 i,j も含まれることに注意してください。

\displaystyle \sum_{0\le i \le j < N} f(i,j) の値を求めてください。

制約

  • 2\le N\le 2\times 10^5
  • 0\le u_i < v_i < N
  • 入力で与えられるグラフは木
  • 入力される値は全て整数

入力

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

N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}

出力

\displaystyle \sum_{0\le i \le j < N} f(i,j) の値を出力せよ。

入力例 1

2
0 1

出力例 1

3

f(0,0)=1,f(0,1)=2,f(1,1)=0 です。したがって、 1+2+0=3 を出力してください。

入力例 2

5
0 1
0 2
2 3
2 4

出力例 2

16

入力例 3

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

出力例 3

16

Score : 525 points

Problem Statement

You are given a tree T with N vertices. The vertices are numbered from 0 to N-1, and the i-th edge (1\le i\le N-1) bidirectionally connects vertices u_i and v_i. (Note that vertex numbers are 0-indexed and edge numbers are 1-indexed.)

For a pair of integers (i,j) where 0 \leq i,j < N, define f(i,j) as follows:

  • The vertex number of the vertex with the smallest number among the vertices not included in the path from vertex i to vertex j in tree T.
    • Here, if the path from vertex i to vertex j includes all vertices from vertex 0 to vertex N-1, let f(i,j)=N.

Note that the path from vertex i to vertex j in tree T includes vertices i and j.

Find the value of \displaystyle \sum_{0\le i \le j < N} f(i,j).

Constraints

  • 2\le N\le 2\times 10^5
  • 0\le u_i < v_i < N
  • The graph given in the input is a tree.
  • All input values are integers.

Input

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

N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}

Output

Output the value of \displaystyle \sum_{0\le i \le j < N} f(i,j).

Sample Input 1

2
0 1

Sample Output 1

3

We have f(0,0)=1,f(0,1)=2,f(1,1)=0. Thus, output 1+2+0=3.

Sample Input 2

5
0 1
0 2
2 3
2 4

Sample Output 2

16

Sample Input 3

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

Sample Output 3

16