← 返回题目列表

AtCoder · arc125_f

F. 树度子集和

中文机器翻译题面 查看原题

分数: 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