解题思路

• 将初始网络视为一片森林（题目保证无环）。森林中每个连通块是一棵树，记其直径为 $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$，最佳策略是：

     • 先把直径最大的两块相连，得到价值 $d_1+d_2+1$；
     • 再依次把剩余块从大到小“接在当前大块的直径端点上”，第 $t$ 次（从 2 开始）连接得到的价值为“当前直径 + 新块直径 + 1”。
     • 交换论证可知：越早参与合并的块在后续多次价值中被重复累加，故应让直径大的块越早合并以最大化总和。

• 实现步骤：

  1. 用两次 BFS/DFS 计算每个连通块的直径（任取一点 BFS 得到最远点 $u$，再以 $u$ BFS 得到最大距离即直径）。

  2. 收集所有直径，按从大到小排序。

  3. 若仅 1 个连通块，答案为 0；否则：

     • 令 cur = d1 + d2 + 1，ans = cur；
     • 依次对 $i=3..K$：ans += cur + di + 1，并更新 cur += di + 1。

该贪心等价于把所有连通块“首尾相接”成一条最长链，每一步都取最大可能直径，累计总价值即最优。

复杂度分析

• 计算所有直径：总计对每个点和边进行常数次 BFS，时间复杂度 $O(N+M)$。
• 排序直径：$O(K\log K)$，其中 $K\le N$。
• 累加答案：$O(K)$。
• 总时间复杂度：$O(N+M+K\log K)$，空间复杂度：$O(N+M)$。

代码实现

Python

# -*- coding: utf-8 -*-
# 题意：森林中加最少边使全连通，并最大化每次合并后连通块直径之和
import sys
from collections import deque

def bfs(src, g, collect):
    """从 src 开始 BFS
    collect=True 时收集该连通块所有节点用于标记已访问
    返回：(最远点, 最远距离, [节点列表/若不收集则为空])
    """
    n = len(g) - 1
    dist = [-1] * (n + 1)
    q = deque([src])
    dist[src] = 0
    nodes = []
    far, dmax = src, 0
    while q:
        u = q.popleft()
        if collect:
            nodes.append(u)
        if dist[u] > dmax:
            dmax, far = dist[u], u
        for v in g[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                q.append(v)
    return (far, dmax, nodes) if collect else (far, dmax, [])

def solve():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    N = int(next(it)); M = int(next(it))
    g = [[] for _ in range(N + 1)]
    for _ in range(M):
        x = int(next(it)); y = int(next(it))
        g[x].append(y); g[y].append(x)

    visited = [False] * (N + 1)
    diams = []  # 各连通块直径
    for u in range(1, N + 1):
        if not visited[u]:
            # 第一次 BFS：找到该连通块内最远点，并收集节点做 visited 标记
            s, _, nodes = bfs(u, g, True)
            for w in nodes:
                visited[w] = True
            # 第二次 BFS：以最远点为源，得到直径
            _, d, _ = bfs(s, g, False)
            diams.append(d)

    K = len(diams)
    if K <= 1:
        print(0)
        return

    diams.sort(reverse=True)
    # 先合并两块最大的
    cur = diams[0] + diams[1] + 1
    ans = cur
    # 依次把剩余从大到小接上
    for i in range(2, K):
        ans += cur + diams[i] + 1
        cur += diams[i] + 1

    print(ans)

if __name__ == "__main__":
    solve()

Java

// 题意：森林中加最少边使全连通，并最大化每次合并后连通块直径之和
import java.io.*;
import java.util.*;

public class Main {
    static ArrayList<Integer>[] g;

    // BFS：collect=true 时收集连通块节点列表，返回 {最远点, 最远距离}
    static int[] bfs(int src, boolean collect, ArrayList<Integer> nodes) {
        int n = g.length - 1;
        int[] dist = new int[n + 1];
        Arrays.fill(dist, -1);
        Deque<Integer> q = new ArrayDeque<>();
        q.add(src);
        dist[src] = 0;
        int far = src, dmax = 0;
        while (!q.isEmpty()) {
            int u = q.poll();
            if (collect) nodes.add(u);
            if (dist[u] > dmax) {
                dmax = dist[u];
                far = u;
            }
            for (int v : g[u]) {
                if (dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    q.add(v);
                }
            }
        }
        return new int[]{far, dmax};
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] first = br.readLine().trim().split("\\s+");
        int N = Integer.parseInt(first[0]);
        int M = Integer.parseInt(first[1]);
        g = new ArrayList[N + 1];
        for (int i = 0; i <= N; i++) g[i] = new ArrayList<>();
        for (int i = 0; i < M; i++) {
            String[] xy = br.readLine().trim().split("\\s+");
            int x = Integer.parseInt(xy[0]);
            int y = Integer.parseInt(xy[1]);
            g[x].add(y);
            g[y].add(x);
        }

        boolean[] vis = new boolean[N + 1];
        ArrayList<Integer> diams = new ArrayList<>();
        for (int u = 1; u <= N; u++) {
            if (!vis[u]) {
                ArrayList<Integer> nodes = new ArrayList<>();
                int[] r1 = bfs(u, true, nodes); // 找到连通块中的一个最远点
                for (int w : nodes) vis[w] = true;
                int[] r2 = bfs(r1[0], false, null); // 从最远点出发得到直径
                diams.add(r2[1]);
            }
        }

        int K = diams.size();
        if (K <= 1) {
            System.out.println(0);
            return;
        }

        diams.sort(Comparator.reverseOrder());
        long cur = (long) diams.get(0) + diams.get(1) + 1;
        long ans = cur;
        for (int i = 2; i < K; i++) {
            ans += cur + diams.get(i) + 1L;
            cur += diams.get(i) + 1L;
        }
        System.out.println(ans);
    }
}

C++

// 题意：森林中加最少边使全连通，并最大化每次合并后连通块直径之和
#include <bits/stdc++.h>
using namespace std;

pair<int,int> bfs(int src, const vector<vector<int>>& g, vector<int>* nodes) {
    int n = (int)g.size() - 1;
    vector<int> dist(n + 1, -1);
    queue<int> q;
    q.push(src);
    dist[src] = 0;
    int far = src, dmax = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (nodes) nodes->push_back(u); // 收集连通块节点
        if (dist[u] > dmax) { dmax = dist[u]; far = u; }
        for (int v : g[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    return {far, dmax};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M;
    if (!(cin >> N >> M)) return 0;
    vector<vector<int>> g(N + 1);
    for (int i = 0; i < M; ++i) {
        int x, y; cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    vector<char> vis(N + 1, 0);
    vector<long long> diams;
    for (int u = 1; u <= N; ++u) {
        if (!vis[u]) {
            vector<int> nodes;
            auto r1 = bfs(u, g, &nodes); // 找到连通块中的一个最远点
            for (int w : nodes) vis[w] = 1;
            auto r2 = bfs(r1.first, g, nullptr); // 从最远点出发得到直径
            diams.push_back((long long)r2.second);
        }
    }

    int K = (int)diams.size();
    if (K <= 1) {
        cout << 0 << "\n";
        return 0;
    }

    sort(diams.begin(), diams.end(), greater<long long>());
    long long cur = diams[0] + diams[1] + 1;
    long long ans = cur;
    for (int i = 2; i < K; ++i) {
        ans += cur + diams[i] + 1;
        cur += diams[i] + 1;
    }
    cout << ans << "\n";
    return 0;
}

题目内容

多多管理着 $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

输出

3

说明

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

样例2

输入

5 3
1 2
1 3
1 4

输出

3

说明

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

样例3

输入

5 2
1 2
3 4

输出

7

说明

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

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

因此输出总价值 $7$ 。