← 返回题目列表

AtCoder · toyota2023spring_final_g

G. 练好Git

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

配点 : 1300 点

問題文

编程初学者 S 君写了如下代码。

N = read_integer()

parent = array(N, -1) //長さ N の配列 parent を作り,すべての要素を -1 で初期化

find(v):
    if parent[v] == -1:
        return v
    else:
        return find(parent[v])

union(a,b):
    parent[find(b)] = find(a)

for i = 0 to N-2:
    A_i = read_integer()
    B_i = read_integer()
    union(A_i,B_i)

这是,N 一个接收树的顶点信息,并仅用Union-Find连接边的程序。

编程高手Ringo注意到这个程序存在缺陷。也就是说,Union-Find完全没有进行任何加速优化。

现在,Ringo有 N 顶点树 有 T 到 T 的顶点上 0 减去 N-1 的编号,边上有 0 减去 N-2 到的编号。 i 是顶点 是 A_i 和边 B_i 是要连接的边。

Ringo打算将其作为输入提供给S君的程序。 不过在此之前, T 可以自由交换边的编号以及边的端点顺序。T Ringo为了证明S君的程序效率低下,

想要最大化函数被调用的次数。find 请找到函数调用次数的最大值。 find 函数必定被调用

制約

  • 2 \leq N \leq 2000
  • 0 \leq A_i,B_i \leq N-1
  • A_i \neq B_i
  • 输入图是一棵树

入力

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

N
A_0 B_0
A_1 B_1
\vdots
A_{N-2} B_{N-2}

出力

打印答案。


入力例 1

2
0 1

出力例 1

2

find 次。 2 调换[[]]端点顺序,并生成如下输入,


入力例 2

3
0 1
0 2

出力例 2

5

辺 0 函数将被调用find 调整边的顺序和端点顺序,生成如下输入, 5 调换[[]]端点顺序,并生成如下输入,

3
1 0
0 2

入力例 3

5
0 1
0 2
0 3
3 4

出力例 3

13

关于find 调整边的顺序和端点顺序,生成如下输入, 13 调换[[]]端点顺序,并生成如下输入,

5
3 0
4 3
1 0
0 2

入力例 4

20
6 16
10 6
16 8
1 5
9 4
5 3
13 16
19 10
12 2
14 10
12 18
0 2
15 16
12 7
11 14
1 10
6 4
17 8
12 1

出力例 4

148