[R26E]树上三元组 - 代码源竞赛平台

时空限制

1S/512M

题目描述

给定一棵由 $n$ 个节点和 $n-1$ 条边组成的树，节点编号从 $1$ 到 $n$。

你需要找出满足以下所有条件的三元组 $(u, v, w)$ 的数量：

1. $u, v, w$ 是三个不同的节点。
2. 节点的编号满足 $u < v$。
3. 节点 $w$ 不在节点 $u$ 和节点 $v$ 之间的简单路径上（路径包含端点 $u$ 和 $v$）。

格式

输入格式

第一行包含一个整数 $n$，表示节点的数量。

接下来的 $n-1$ 行，每行包含两个整数 $u, v$，表示节点 $u$ 和节点 $v$ 之间存在一条边。

输出格式

输出一个整数，表示满足条件的三元组的总数。

样例

样例输入 #1

4
1 2
1 3
1 4

样例输出 #1

9

样例解释 #1

该树的结构为节点 $1$ 连接着节点 $2, 3, 4$。

枚举所有满足 $u<v$ 的点对 $(u, v)$:

• $(u,v) = (1, 2)$：路径为 $1 \to 2$。路径上的节点为 $\{1, 2\}$。$w$ 可以是 $3$ 或 $4$。可以得到满足条件的三元组为 $(1, 2, 3)$ 和 $(1, 2, 4)$。

• $(u,v) = (1, 3)$：路径为 $1 \to 3$。路径上的节点为 $\{1, 3\}$。$w$ 可以是 $2$ 或 $4$。 可以得到满足条件的三元组为三元组 $(1, 3, 2)$ 和 $(1, 3, 4)$。

• $(u,v) = (1, 4)$：路径为 $1 \to 4$。路径上的节点为 $\{1, 4\}$。$w$ 可以是 $2$ 或 $3$。 可以得到满足条件的三元组为三元组 $(1, 4, 2)$ 和 $(1, 4, 3)$。

• $(u,v) = (2, 3)$：路径为 $2 \to 1 \to 3$。路径上的节点为 $\{1, 2, 3\}$。$w$ 只能是 $4$。 可以得到满足条件的三元组为三元组 $(2, 3, 4)$。

• $(u,v) = (2, 4)$：路径为 $2 \to 1 \to 4$。路径上的节点为 $\{1, 2, 4\}$。$w$ 只能是 $3$。 可以得到满足条件的三元组为三元组 $(2, 4, 3)$。

• $(u,v) = (3, 4)$：路径为 $3 \to 1 \to 4$。路径上的节点为 $\{1, 3, 4\}$。$w$ 只能是 $2$。 可以得到满足条件的三元组为三元组 $(3, 4, 2)$。

故总方案数为 $2 + 2 + 2 + 1 + 1 + 1 = 9$。

数据规模

对于 $30\%$ 的数据， $2 \leq n \leq 100$。

对于 $50\%$ 的数据， $2 \leq n \leq 1000$。

对于 $100\%$ 的数据，$2 \leq n \leq 5 \times 10^5$，$1 \leq u, v \leq n$，且输入的边保证构成一棵树。