← 返回题目列表

Codeforces · 891/D

D. 树懒

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

懒惰是不好的,好吗?所以我们决定准备一个问题来惩罚懒惰的人。

给定一棵树,您应该计算从中删除边的方法的数量,然后向其添加边,以便最终的图是一棵树并且具有完美匹配。如果删除的边或添加的边不相同,则该操作的两种方式被认为是不同的。移除的边和添加的边可以相等。

完美匹配是边的子集,使得每个顶点恰好是这些边之一的端点。

输入

第一行包含 n (2 ≤ n ≤ 5·105) — 顶点数。

接下来的 n - 1 行中的每一行都包含两个整数 a 和 b (1 ≤ a, b ≤ n) — 一条边的端点。保证该图是一棵树。

输出

输出一个整数——问题的答案。

示例

输入 #1

4
1 2
2 3
3 4

输出 #1

8

输入 #2

5
1 2
2 3
3 4
3 5

输出 #2

0

输入 #3

8
1 2
2 3
3 4
1 5
5 6
6 7
1 8

输出 #3

22

注意

在第一个示例中,有 8 种方式:

- 2 和 3 之间的边转向 1 和 3 之间的边,
- 2 和 3 之间的边转向 1 和 4 之间的边,
- 2 和 3 之间的边转向 2 和 3 之间的边,
- 2 和 3 之间的边转向 2 和 4 之间的边,
- 1 和 2 之间的边变成 1 和 2 之间的边,
- 1 和 2 之间的边变成 1 和 4 之间的边,
- 3 和 4 之间的边转向 1 和 4 之间的边,
- 3 和 4 之间的边缘转向 3 和 4 之间的边缘。