题目描述

给定一棵包含 $N$ 个顶点的树。顶点从 $1$ 到 $N$ 编号，第 $i$ 个边连接顶点 $A_i$ 和顶点 $B_i$。

找到满足以下条件的整数对 $(x,y)$ 的数量。

• $0 \\leq x \\leq N$。

• 存在一种方式从树中选择恰好 $x$ 个顶点，使得它们的度之和等于 $y$。

约束条件

• $2 \\leq N \\leq 2 \\times 10^5$
• $1 \\leq A_i < B_i \\leq N$
• 输入中的所有值均为整数。

输入

输入以以下格式从标准输入中给出：

$N$ $A_1$ $B_1$ $A_2$ $B_2$ $\\vdots$ $A_{N-1}$ $B_{N-1}$

输出

打印答案。

示例输入 1

3
1 2
2 3

示例输出 1

6

满足条件的六个整数对 $(x,y)$ 如下所示。

• $x=0,y=0$
• $x=1,y=1$
• $x=1,y=2$
• $x=2,y=2$
• $x=2,y=3$
• $x=3,y=4$

例如，当选择顶点 $1$ 和顶点 $2$ 时，$x=2,y=3$ 满足条件，因为它们的总度数是 $3$。

示例输入 2

5
1 2
2 3
2 4
4 5

示例输出 2

16

示例输入 3

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

示例输出 3

65