配点 : $900$ 点

問題文

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

出力

答えを出力せよ．

3
1 2
2 3

6

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

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