#5615. 「PA 2016 Final」Skojarzenie

标签: 传统 | 时间限制: 2500 ms | 内存限制: 256 MiB |

题目描述

在图 $G=(V, E)$ 中，我们称边的一个子集 $M$ 为一个匹配，如果 $M$ 中的任意两条边都没有公共端点。

对于图 $G$ 中一对不相邻的顶点 $(u, v)$ （满足 $u \neq v$ 且 $(u, v) \notin E$ ），如果将边 $(u, v)$ 添加到 $G$ 中会导致 $G$ 的最大匹配规模增大，则称这对顶点是有前途的。

给定一个包含 $n$ 个顶点和 $n-1$ 条边的连通图* $G$ 。你需要计算图 $G$ 中有前途的顶点对的数量。

第一行包含一个整数 $n$ $(1 \leq n \leq 200000)$ ，表示图 $G$ 的顶点数。

接下来的 $n-1$ 行包含图 $G$ 的边描述。其中第 $i$ 行包含两个整数 $a_{i}$ 和 $b_{i}$ $(1 \leq a_{i}, b_{i} \leq n)$ ，表示第 $i$ 条边连接顶点 $a_{i}$ 和 $b_{i}$ 。

我们假设图 $G$ 的顶点编号为从 $1$ 到 $n$ 。

输出一个整数，即图 $G$ 中有前途的顶点对的数量。

输入

输出

唯一有前途的顶点对是 $(3,4), (3,5)$ 和 $(4,5)$ 。