题目描述

编程初学者すぬけくん写了如下代码。

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 仅仅连接边。

编程大师りんごさん注意到了这个程序的缺陷。也就是说，这个 Union-Find 并没有做任何优化。

现在，りんごさん有一棵包含 $N$ 个顶点的树 $T$。$T$ 的顶点编号为 $0$ 到 $N-1$，边的编号为 $0$ 到 $N-2$。第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$。

りんごさん打算将 $T$ 作为输入给すぬけくん的程序。不过在此之前，他可以自由地重新排列 $T$ 的边的编号，以及每条边的两个端点的顺序。

りんごさん想要最大化 find 函数被调用的次数，以此来展示すぬけくん的程序效率低下。请你求出 find 函数被调用次数的最大值。

输入格式

输入通过标准输入给出，格式如下：

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

输出格式

请输出答案。

输入输出样例 #1

输入 #1

2
0 1

输出 #1

2

输入输出样例 #2

输入 #2

3
0 1
0 2

输出 #2

5

输入输出样例 #3

输入 #3

5
0 1
0 2
0 3
3 4

输出 #3

13

输入输出样例 #4

输入 #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

说明/提示

限制条件

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

样例解释 1

find 函数一定会被调用 $2$ 次。

样例解释 2

将第 $0$ 条边的端点顺序交换，构造成如下输入，则 find 函数会被调用 $5$ 次。

3 1 0 0 2

样例解释 3

通过适当调整边的顺序和端点顺序，构造成如下输入，则 find 函数会被调用 $13$ 次。

5 3 0 4 3 1 0 0 2

由 ChatGPT 4.1 翻译