[ARC125F] Tree Degree Subset Sum
题意翻译
给定一棵 $N$ 个点的树，第 $i$ 条边连接了 $A_i$ 和 $B_i$ 两个节点。求出满足以下条件的数对 $(x,y)$ 的个数：
- $0\le x\le N$；
- 存在一种从树上选出恰好 $x$ 个节点的方案，使得节点的度数和为 $y$。
$2\le N\le 2\times 10^5$。
题目描述
[problemUrl]: https://atcoder.jp/contests/arc125/tasks/arc125_f
$ 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} $
输出格式
答えを出力せよ．
输入输出样例
输入样例 #1
3
1 2
2 3输出样例 #1
6输入样例 #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说明
### 制約
- $ 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 $ は条件を満たします．