避开直线

题目描述

给定一棵有 $N$ 个顶点的树。顶点编号为 $1$ 到 $N$,第 $i$ 条边连接顶点 $A_i$ 和 $B_i$。

求满足以下条件的整数三元组 $(i,j,k)$ 的个数:

• $1 \le i \lt j \lt k \le N$;且
• 给定的树中,不存在同时包含顶点 $i$、$j$、$k$ 的简单路径。

输入格式

输入按以下格式从标准输入给出:

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

输出格式

输出答案。

样例

5
1 2
2 3
2 4
1 5

2

满足条件的三元组有两个:$(i,j,k) = (1,3,4),(3,4,5)$。

6
1 2
2 3
3 4
4 5
5 6

0

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

91

数据范围

• $1 \le N \le 2 \times 10^5$
• $1 \le A_i, B_i \le N$
• 给定的图是一棵树。
• 所有输入值均为整数。