Contest Duration: - (local time) (120 minutes) Back to Home
F - Tree Degree Subset Sum /

Time Limit: 6 sec / Memory Limit: 1024 MB

### 問題文

N 頂点からなる木が与えられます． 頂点には 1 から N までの番号がついており，i 番目の辺は頂点 A_i と頂点 B_i を結んでいます．

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


### 入力例 1

3
1 2
2 3


### 出力例 1

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

### 入力例 2

5
1 2
2 3
2 4
4 5


### 出力例 2

16


### 入力例 3

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


### 出力例 3

65


Score : 900 points

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


### 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