← 返回题目列表

AtCoder · past20_l

L. 直径对

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

问题陈述

你得到了一棵树 N 顶点。 的 i第一条边连接顶点 A_i 和 B_i.

两个顶点之间的距离 x 和 y 是路径中可能的最小边数 x to y。 树的直径是两个顶点之间的最大距离。

让 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

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