CF437D The Child and Zoo

CF437D The Child and Zoo - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

很像货车运输？但是点权？转化一下。每条边 \((u, v)\) 设定边权为 \(\min(a[u], a[v])\)，那么一条简单路径的点权最小值和边权最小值就是等价的。

根据货车运输的思想，最大生成树上 \(u\) 到 \(v\) 的简单路径，肯定是原图 \(u\) 到 \(v\) 的那条边权最小值最大的路径。

点对数量 \(n^2\) 明显不支持枚举，但所有点对的 \(f\) 肯定只能是 \(m\) 个边权中的某一个，这启发我们计算每条边的贡献。

发现在最大生成树的连边过程中，每连一条边 \((u, v, w)\) 就把 \(u\) 所在连通块和 \(v\) 所在连通块合并了。此时，\(u\) 所在连通块中任意一个点 \(x\) 到达 \(v\) 所在连通块中任意一个点 \(y\) 的简单路径边权最小值一定是 \(w\)。

证明：连接 \((u, v)\) 后，点 \(x\) 到点 \(y\) 在最大生成树上的简单路径就出现了（之前不连通）。由于我们从大到小选边，所以这条简单路径上最小的边权一定是 \(w\)。

因此一条边的贡献是 \(siz[u] \times siz[v] \times w \times 2\)。其中 \(\times 2\) 是因为 \((p, q)\) 和 \((q, p)\) 都需要统计一次。\(siz[u]\) 是 \(u\) 所在连通块的大小。

容易证明，每一个点对都会恰好被统计一次。最后把结果除以 \(n \times (n - 1)\) 即可得到平均值。

/*
 * @Author: crab-in-the-northeast 
 * @Date: 2022-10-13 23:56:06 
 * @Last Modified by: crab-in-the-northeast
 * @Last Modified time: 2022-10-14 00:06:16
 */
#include <bits/stdc++.h>
#define int long long
inline int read() {
    int x = 0;
    bool flag = true;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-')
            flag = false;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = (x << 1) + (x << 3) + ch - '0';
        ch = getchar();
    }
    if(flag)
        return x;
    return ~(x - 1);
}

const int maxn = (int)1e5 + 5;
const int maxm = (int)1e5 + 5;

struct edge {
    int u, v, w;
}e[maxm];

int a[maxn];

inline int min(int a, int b) {
    return a < b ? a : b;
}

int fa[maxn], siz[maxn];

inline int get(int x) {
    while (x != fa[x])
        x = fa[x] = fa[fa[x]];
    return x;
}

inline void uni(int x, int y) {
    if (siz[x] > siz[y])
        x ^= y ^= x ^= y;
    fa[x] = y;
    siz[y] += siz[x];
}

signed main() {
    int n = read(), m = read();
    for (int i = 1; i <= n; ++i)
        a[i] = read();
    
    for (int i = 1; i <= m; ++i) {
        int u = read(), v = read();
        int w = min(a[u], a[v]);
        e[i] = (edge){u, v, w};
    }

    std :: sort(e + 1, e + 1 + m, [](edge a, edge b) {
        return a.w > b.w;
    });

    std :: iota(fa + 1, fa + 1 + n, 1);
    std :: fill(siz + 1, siz + 1 + n, 1);
    
    int ans = 0;
    for (int i = 1; i <= m; ++i) {
        int u = e[i].u, v = e[i].v, w = e[i].w;
        u = get(u);
        v = get(v);
        if (u == v)
            continue;
        ans += 2 * siz[u] * siz[v] * w;
        uni(u, v);
    }

    printf("%.6f\n", ans * 1.0 / (n * (n - 1)));
    return 0;
}