AT_arc125_f [ARC125F] Tree Degree Subset Sum

给定一棵包含 $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)$ 的对数。

## 限制条件 - $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 翻译