103126: [Atcoder]ABC312 G - Avoid Straight Line

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

问题描述

给你一棵有N个顶点的树。顶点编号从1到N，第i条边连接顶点A_i和顶点B_i。

找到满足以下条件的整数元组(i,j,k)的数量：

• 1 ≤ i < j < k ≤ N；以及
• 给定的树中不存在包含顶点i、j和k的简单路径。

限制条件

• 1 ≤ N ≤ 2 × 10^5
• 1 ≤ A_i, B_i ≤ 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

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