解题思路

将初始网络视为一片森林（题目保证无环）。森林中每个连通块是一棵树，记其直径为 $d_i$ （任意两点最远距离，边长均为 1）。
关键结论：
1. 用一条新边把两棵树相连时，若把两树各自“直径的端点”相连，则新连通块的直径为 $\displaystyle d_{\text{new}}=d_a+d_b+1$ 。这是该次连接可获得的最大值（因为跨两树的最长路径由两侧各自最远点经新边连接组成，且 $\max(d_a,d_b)\le d_a+d_b+1$ ）。
2. 设初始有 $K$ 个连通块，则最少需要加 $K-1$ 条边。若将各块按直径从大到小排序为 $d_1\ge d_2\ge\cdots\ge d_K$ ，最佳策略是：

P4461.第4题-多多的集群

1000ms

Tried: 30

Accepted: 13

Difficulty: 7

所属公司 : 拼多多

算法与标签>BFS贪心

题目内容

多多管理着 $N$ 台服务器主机（编号为 $1$ 到 $N$ ），这些主机之间已经建立了 $M$ 条网络连接（保证不存在环）。

作为一名资深工程师，您现在需要添加新的网络连接，将所有主机连通形成一个统一的服务器集群。

每次添加新连接时，都会产生相应的价值收益，价值的计算方式是：

每条网络连接的长度均为 $1$
当连接两台主机后，与这两台主机连通的所有主机会形成一个连通块
在这个连通块中，任意两台主机之间的最长路径就是本次连接产生的价值
初始价值为 $0$ ，最终的总价值是每次添加连接产生的价值之和

您的目标是在添加最少新连接（使得整个网络连通）的前提下，最大化总价值。

输入描述

第一行输入 $N$ 和 $M,N$ 表示主机的数量（ $1 ≤ N ≤ 10^5$ ）， $M$ 表示初始网络连接的数量（ $0 ≤ M < N$ ）

接下来 $M$ 行，每行输入 $x$ 和 $y$ ，其中 $1 ≤ x, y ≤ N$

输出描述

输出一个数，表示集群连通后产生的最大价值

补充说明

集群中保证不存在环，且每条网络连接的长度均为 $1$

样例1

输入

4 2
1 2
3 4

输出

说明

将 $2$ 和 $3$ 相连，因此最大距离为 $1$ $- 2$ $- 3$ $- 4$

样例2

输入

输出

说明

将 $2$ 和 $5$ 相连，某条最大直径为 $2$ $- 1$ $- 3$ $- 5$ 。

样例3

输入

5 2
1 2
3 4

输出

说明

先将 $(1, 2)$ 和 $(3, 4)$ 相连，产生价值 $3$ ，

再将 $(1, 2, 3, 4)$ 和 $(5)$ 相连，产生价值 $4$ ，

因此输出总价值 $7$ 。

输入

预期输出（选填）

解题思路

P4461.第4题-多多的集群

题目内容

输入描述

输出描述

补充说明

样例1

样例2

样例3

Status

Development

Support

About