分数: 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) 满足条件。
- 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满足条件,因为选择 Vertex 1 和顶点 2 达到总度 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