F - Add One Edge 2 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 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

Score : 500 points

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