AT_abc312_g [ABC312G] Avoid Straight Line
题目描述
给定一棵有 $N$ 个顶点的树。顶点编号为 $1$ 到 $N$，第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$。
请计算满足以下条件的整数三元组 $(i, j, k)$ 的个数。
- $1 \leq i < j < k \leq N$
- 在给定的树中，不存在一条简单路径包含顶点 $i, j, k$。
输入格式
输入以如下格式从标准输入读入。
> $N$
> $A_1$ $B_1$
> $\vdots$
> $A_{N-1}$ $B_{N-1}$
输出格式
请输出答案。
说明/提示
## 限制条件
- $1 \leq N \leq 2 \times 10^5$
- $1 \leq A_i, B_i \leq N$
- 给定的图是一棵树
- 输入的所有值均为整数
## 样例解释 1
满足条件的 $(i, j, k)$ 有 $(1,3,4)$ 和 $(3,4,5)$，共 $2$ 组。
由 ChatGPT 4.1 翻译