思路

如果两个被占领的城市之间存在一条道路，那么就可以用并查集合并。对于两个集合的合并：

• 集合 中所有元素与集合 中所有元素建立一条连边，总共 条。

先统计所有占领的联通块内部能获得多少收益，然后遍历所有未占领的城市，尝试将其与所有相邻的占领连通块合并，计算出收益增量，取其中最高的一个。

小妙招

记一个 cnt = 1 表示未占领节点被占领，将其与其中一个相邻占领连通块合并，这会使收益增量 ansNum += cnt * size[get(v)]，然后他们就属于同一个集合内，可记 cnt += size[get(v)]，循环利用这两个变量即可。

记得

• 开 long long
• 对于一个未占领节点，它的两个相邻占领节点可能已经来自同一个占领连通块，记得去重。

代码 (C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

constexpr int N = 100005;

int n, m;
ll a[N], siz[N];
bool vis[N];
vector<int> edges[N];

void init() {
    for (int i = 1; i <= n; i++) {
        a[i] = i;
        siz[i] = 1;
    }
}

int get(int x) {
    if (a[x] == x) return x;
    a[x] = get(a[x]);
    return a[x];
}

ll ans = 0;

void merge(int x, int y) {
    if (get(x) == get(y)) return ;
    ans += siz[get(x)] * siz[get(y)];
    siz[get(y)] += siz[get(x)];
    a[get(x)] = get(y);
}

int main() {
    scanf("%d %d\n", &n, &m);
    init();
    string str; getline(std::cin, str);
    for (int i = 1; i <= n; i++) {
        if (str[i - 1] == '1') vis[i] = true;
    }

    for (int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        if (vis[u] && vis[v]) merge(u, v);
        edges[u].push_back(v);
        edges[v].push_back(u);
    }

    int ansU = -1; ll ansNum = 0;
    for (int u = 1; u <= n; u++) {
        if (vis[u]) continue;
        set<int> visited;
        ll cnt = 1; ll sum = 0;
        for (int v : edges[u]) {
            if (!vis[v]) continue;
            if (visited.find(get(v)) != visited.end()) continue;
            visited.insert(get(v));
            sum += cnt * siz[get(v)];
            cnt += siz[get(v)];
        }
        if (sum > ansNum) { ansU = u; ansNum = sum; }
    }

    cout << ansU << " " << ans + ansNum << endl;
}