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