题目描述

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

请计算有多少对整数 $(x, y)$ 满足以下条件：

• $0 \leq x \leq N$；
• 可以从树中恰好选出 $x$ 个顶点，使得它们的度数之和恰好为 $y$。

输入格式

输入以如下格式从标准输入读入：

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

输出格式

请输出满足条件的 $(x, y)$ 的对数。

样例 1

输入

3
1 2
2 3

输出

6

样例 2

输入

5
1 2
2 3
2 4
4 5

输出

16

样例 3

输入

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

输出

65

说明/提示

限制条件

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq A_i < B_i \leq N$
• 输入的图保证为一棵树。

样例解释 1

满足条件的 $(x, y)$ 共有以下 $6$ 种情况：

• $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$ 时，度数之和为 $3$，因此 $x=2, y=3$ 满足条件。

由 ChatGPT 4.1 翻译