分数: 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
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