G - Avoid Straight Line Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 550 点

問題文

N 頂点の木が与えられます。頂点には 1 から N までの番号がついており、i 番目の辺は頂点 A_i と頂点 B_i を結んでいます。
以下の条件を満たす整数の組 (i,j,k) の個数を求めてください。

  • 1 \leq i < j < k \leq N
  • 与えられた木には頂点 i,j,k をすべて含む単純パスは存在しない

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i, B_i \leq N
  • 与えられるグラフは木
  • 入力される値はすべて整数

入力

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

N
A_1 B_1
\vdots
A_{N-1} B_{N-1}

出力

答えを出力せよ。

入力例 1

5
1 2
2 3
2 4
1 5

出力例 1

2

(i,j,k) = (1,3,4),(3,4,5) の 2 つが条件を満たします。

入力例 2

6
1 2
2 3
3 4
4 5
5 6

出力例 2

0

入力例 3

12
1 6
3 4
10 4
5 9
3 1
2 3
7 2
2 12
1 5
6 8
4 11

出力例 3

91

Score : 550 points

Problem Statement

You are given a tree with N vertices. The vertices are numbered from 1 through N, and the i-th edge connects vertex A_i and vertex B_i.
Find the number of tuples of integers (i,j,k) such that:

  • 1 \leq i < j < k \leq N; and
  • the given tree does not contain a simple path that contains all of vertices i, j, and k.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i, B_i \leq N
  • The given graph is a tree.
  • All input values are integers.

Input

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

N
A_1 B_1
\vdots
A_{N-1} B_{N-1}

Output

Print the answer.

Sample Input 1

5
1 2
2 3
2 4
1 5

Sample Output 1

2

Two tuples satisfy the conditions: (i,j,k) = (1,3,4),(3,4,5).

Sample Input 2

6
1 2
2 3
3 4
4 5
5 6

Sample Output 2

0

Sample Input 3

12
1 6
3 4
10 4
5 9
3 1
2 3
7 2
2 12
1 5
6 8
4 11

Sample Output 3

91