F - Tree Degree Subset Sum Editorial /

Time Limit: 6 sec / Memory Limit: 1024 MiB

配点 : 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}

出力

答えを出力せよ．

入力例 1

3
1 2
2 3

出力例 1

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

入力例 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}

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