Public Judge

pjudge

Time Limit: 2 s Memory Limit: 1024 MB Total points: 100

# 21808. 【PR #12】并查集

Statistics

题目描述

如下是一份并查集的代码实现:

N = read_integer()
parent = array(N, -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)

这份代码的输入是一棵标号从 $0$ 到 $n-1$ 的树,每次读入一条边 $(A_i,B_i)$ ,并用并查集把 $A_i,B_i$ 所在的连通块合并。但是这份代码有一个问题:它的 find(v) 没有实现路径压缩,因此它的复杂度是错的。

作为省选的出题人,你当然不能容许复杂度错误的并查集通过你的题目。

给定一棵树,你可以把边的顺序任意打乱,并对每条边都可以交换 $A_i,B_i$​ (也可以不交换),求出以上代码调用 find(v) 的最大次数。

输入格式

第一行一个正整数 $n$ ,表示点数。

接下来 $n-1$ 行,每行两个非负整数 $A_i,B_i$ ,表示一条边。

输出格式

输出一行一个正整数,表示答案。

样例

样例输入 1

3
0 1
0 2

样例输出 1

5

样例解释

重排之后的输入是

3
1 0
0 2

样例输入 2

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

样例输出 2

41

样例 3

见下发文件。

数据范围

对于全部数据,保证 $1\le n\le 2000,0\le A_i,B_i\le n-1$ ,保证输入是一棵树。

子任务编号 特殊性质 分值
$1$ $n\le 9$ $15$
$2$ $n\le 11$ $15$
$3$ $n\le 16$ $15$
$4$ 输入是一条链 $15$
$5$ 存在一个 $k$ ,使得每个点的度数是 $1$ 或 $k$ $10$
$6$ $n\le 100$ $15$
$7$ $ $ $15$