← 返回题目列表

AtCoder · abc312_g

G. 避免直线

中文机器翻译题面 查看原题

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