← 返回题目列表

AtCoder · typical90_c

003. 最长的环形路(★4)

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

配点: 4 点

問題文

N 有个城市,每个城市都有 1 减去 N 以内的编号。 此外,N-1 有一条路,i 本目 (1 \leq i \leq N-1) 的道路连接城市 A_i 和城市 它连接 B_i 是双向连接的。无论哪两个城市之间,都可以通过几条道路进行移动。

现在,你可以自由选择一个整数 u, v (1 \leq u \lt v \leq N) 并在城市 u 和城市 它连接 v 之间新建双向道路 1 条。因此,在以下规定的值中, 分数 。

  • 相同的路径 2 从某个城市出发经过某些道路后又回到同一城市的路径中所经过的道路数量(这个值是唯一确定的) 1 作为得分,

请输出可以考虑的最大值。

制約

  • 3 \leq N \leq 100000
  • 1 \leq A_i \lt B_i \leq N (1 \leq i \leq N-1)
  • 无论哪两个城市之间,都可以通过几条道路进行移动。
  • 给出的所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

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

出力

请输出题目中定义的得分可以考虑的最大值。


入力例 1

3
1 2
2 3

出力例 1

3

都市 1 和城市 3 之间建设道路。这样,经过名为 1 → 都市 2 → 都市 3 → 都市 1 的路径所经过的道路数量为 3 条,并作为得分 3 可以实现。


入力例 2

5
1 2
2 3
3 4
3 5

出力例 2

4

都市 1 和城市 5 之间建设道路。这样,经过名为 1 → 都市 2 → 都市 3 → 都市 5 → 都市 1 的路径所经过的道路数量为 4 条,并作为得分 4 可以实现。


入力例 3

10
1 2
1 3
2 4
4 5
4 6
3 7
7 8
8 9
8 10

出力例 3

8

入力例 4

31
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31

出力例 4

9