• 走访的总代价是 图的极大联通分量数 - 1。

• 新建一条边，减少极大联通分量数的方法如下：

  • 选择两个属于不同联通分量的点 $x,y$，
  • 连接 $x,y$，这样，联通分量就减少一个。

• 设各极大联通分量的点数为 $a_1,a_2,\cdots,a_k$，则答案是：

  • $$\sum_{1\le i<j\le k}a_ia_j$$

  • 这表示

    • 选择两个联通分量 $i,j$，点数分别为 $a_i,a_j$。
    • 任选两个点并联通它们。
    • 方案数为 $a_ia_j$。

关于计算

的值，这是一道蓝桥杯的往年真题。采用暴力算法是 $\Theta(k^2)$ 的，且 $k$ 可以到达 $n$ 的量级。

因此需要优化为 $\Theta(k)$，给出两种策略：

• 方案 $1$：维护前缀和 $s_i=a_1+a_2\cdots+a_i(s_0=0)$，并求解 $\sum_{1\le i\le k}a_is_{i-1}$。

• 方案 $2$：注意到

  $$(a_1+a_2+\cdots+a_k)^2=a_1^2+a_2^2+\cdots+a_k^2+2\times \sum_{1\le i<j\le k}a_ia_j $$

  据此可 $\Theta(k)$ 地取得答案。

求解各联通分量的点数可以采用搜索的方法，时间复杂度是 $\Theta(n)$。

#include <iostream>
#include <vector>
#include <functional>

using namespace std;

void solve() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    vector<int> sizes;
    vector<bool> vis(n + 1, false);

    function<void(int, int&)> dfs = [&](int node, int& size) {
        size++;
        for (int neighbor : adj[node]) {
            if (!vis[neighbor]) {
                vis[neighbor] = true;
                dfs(neighbor, size);
            }
        }
    };

    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            vis[i] = true;
            int size = 0;
            dfs(i, size);
            sizes.push_back(size);
        }
    }

    auto smart_calculation = [](const vector<int>& v) {
        long long sum = 0, sqr_sum = 0;
        for (int i : v) {
            sum += i;
            sqr_sum += (long long)i * i;
        }
        return (sum * sum - sqr_sum) / 2;
    };

    cout << smart_calculation(sizes) << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t; cin >> t; while (t--) 
    solve();

    return 0;
}