配点 : 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