L - Diameter Pairs Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

問題文

N 頂点からなる木が与えられます。i 番目の辺は頂点 A_i, B_i を結んでいます。

木の 2 頂点 x, y の距離は、 x と y を端点とするパスに含まれる辺数として得られる値のうち最小のものです。また、木の直径は任意の 2 頂点間の距離の最大値です。

この木の直径を D とします。頂点の組 (a, b) \ (a < b) であって、頂点 a, b の距離が D であるものの個数を求めてください。

制約

  • 1 \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 行に出力せよ。

入力例 1

5
1 2
1 3
1 4
4 5

出力例 1

2

この木の直径は 3 です。距離が 3 である頂点の組として、 (2, 5), (3, 5) があります。よって 2 を出力します。

入力例 2

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

出力例 2

4

Problem Statement

You are given a tree with N vertices. The i-th edge connects vertices A_i and B_i.

The distance between two vertices x and y on the tree is the minimum possible number of edges in a path from x to y. The diameter of the tree is the maximum distance between two vertices.

Let D be the diameter of this tree. Find the number of pairs of vertices (a, b) \ (a < b) such that the distance between a and b equals D.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i, B_i \leq N
  • The given graph is a tree.

Input

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

N
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}

Output

Print the answer in a single line.

Sample Input 1

5
1 2
1 3
1 4
4 5

Sample Output 1

2

The diameter of this tree is 3. The pairs of vertices distant by 3 are (2, 5) and (3, 5). Thus, 2 should be printed.

Sample Input 2

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

Sample Output 2

4