← 返回题目列表

Codeforces · 862/B

B. Mahmoud 和 Ehab 以及两党性

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

Mahmoud 和 Ehab 继续他们的冒险!邪恶之地的每个人都知道,邪恶博士喜欢二分图,尤其是树。

树是一个连通的非循环图。二分图是一种图,其顶点可以划分为 2 个集合,对于属于该图的每条边 (u, v),u 和 v 属于不同的集合。您可以在下面的注释部分找到树和二分图的更正式的定义。

Evil 博士给了 Mahmoud 和 Ehab 一棵由 n 个节点组成的树,并要求他们以这样的方式向其添加边,使图仍然是二分图。此外,添加这些边后,图形应该很简单(不包含循环或多个边)。他们最多可以添加多少条边?

环是一条边,它将节点与其自身连接起来。当每对节点之间不超过一条边时,图不包含多条边。循环和循环并不相同。

输入

输入的第一行包含一个整数 n — 树中的节点数 (1 ≤ n ≤ 105)。

接下来的 n - 1 行包含整数 u 和 v (1 ≤ u, v ≤ n, u ≠ v) - 树边的描述。

保证给定的图是一棵树。

输出

输出一个整数——Mahmoud 和 Ehab 在满足条件的情况下可以添加到树中的最大边数。

示例

输入 #1

3
1 2
1 3

输出 #1

0

输入 #2

5
1 2
2 3
3 4
4 5

输出 #2

2

注意

树定义:https://en.wikipedia.org/wiki/Tree_(graph_theory)

二分图定义:https://en.wikipedia.org/wiki/Bipartite_graph

在第一个测试用例中,可以以这种方式添加的唯一边(该图不包含循环或多条边)是 (2, 3),但添加此边将使图成为非二分图,因此答案为 0。

在第二个测试用例中,Mahmoud 和 Ehab 可以添加边 (1, 4) 和 (2, 5)。