题目描述

$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}$

输出格式

答えを出力せよ．

题目大意

给定一棵 $N$ 个点的树，第 $i$ 条边连接了 $A_i$ 和 $B_i$ 两个节点。求出满足以下条件的数对 $(x,y)$ 的个数：

• $0\le x\le N$；
• 存在一种从树上选出恰好 $x$ 个节点的方案，使得节点的度数和为 $y$。

$2\le N\le 2\times 10^5$。

3
1 2
2 3

6

5
1 2
2 3
2 4
4 5

16

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$
• 入力されるグラフは木である．

Sample Explanation 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$ は条件を満たします．