103785: [Atcoder]ABC378 F - Add One Edge 2

Problem Statement

You are given a tree with $N$ vertices. The $i$-th edge $(1 \leq i \leq N-1)$ connects vertices $u_i$ and $v_i$ bidirectionally.

Adding one undirected edge to the given tree always yields a graph with exactly one cycle.

Among such graphs, how many satisfy all of the following conditions?

• The graph is simple.
• All vertices in the cycle have degree $3$.

Constraints

• $3 \leq N \leq 2 \times 10^5$
• $1 \leq u_i, v_i \leq N$
• The given graph is a tree.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

6
1 2
2 3
3 4
4 5
3 6

Sample Output 1

1

Adding an edge connecting vertices $2$ and $4$ yields a simple graph where all vertices in the cycle have degree $3$, so it satisfies the conditions.

Sample Input 2

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

Sample Output 2

0

There are cases where no graphs satisfy the conditions.

Sample Input 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

Sample Output 3

6

问题陈述

给你一个有N个顶点的树。第i条边（1 ≤ i ≤ 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