← 返回题目列表

AtCoder · abc378_f

I. 添加一条边 2

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

分数: 500 点

问题陈述

你得到了一棵树 N 顶点。的 i第边缘 (1 \leq i \leq N-1) 连接顶点 u_i 和 v_i 双向。

向给定树添加一条无向边始终会生成一个恰好具有一个循环的图。

在这些图中,有多少个满足以下所有条件?

  • 该图很简单。
  • 循环中的所有顶点都有度数 3.

约束

  • 3 \leq N \leq 2 \times 10^5
  • 1 \leq u_i, v_i \leq N
  • 给定的图是一棵树。
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}

输出

打印答案。


示例输入 1

6
1 2
2 3
3 4
4 5
3 6

示例输出 1

1

添加连接顶点的边 2 和 4 产生一个简单的图,其中循环中的所有顶点都有度数 3,因此满足条件。


示例输入 2

7
1 2
2 7
3 5
7 3
6 2
4 7

示例输出 2

0

存在没有图形满足条件的情况。


示例输入 3

15
1 15
11 14
2 10
1 7
9 8
6 9
4 12
14 5
4 9
8 11
7 4
1 13
3 6
11 10

示例输出 3

6