问题陈述
你得到了一棵树 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