201255: [AtCoder]ARC125 F - Tree Degree Subset Sum

Problem Statement

Given is a tree with $N$ vertices. The vertices are numbered $1$ through $N$, and the $i$-th edge connects Vertex $A_i$ and Vertex $B_i$.

Find the number of pairs of integers $(x,y)$ that satisfy the following conditions.

• $0 \leq x \leq N$.

• There is a way to choose exactly $x$ vertices from the tree so that the sum of their degrees equals $y$.

Constraints

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq A_i < B_i \leq N$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

3
1 2
2 3

Sample Output 1

6

The following six pairs $(x,y)$ satisfy the conditions.

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

$x=2,y=3$, for example, satisfies the condition because choosing Vertex $1$ and Vertex $2$ achieves the total degree of $3$.

Sample Input 2

5
1 2
2 3
2 4
4 5

Sample Output 2

16

Sample Input 3

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

Sample Output 3

65