题目大意

• 给定一个 $n$ 个点，$m$ 条边的无向图，编号为 $i$ 的点的点权为 $a_i$。

• 设 $f(u,\ v)$（$1\leq u,\ v\leq n,\ u\not=v$）表示 一条 $u$ 到 $v$ 路径上最小点权 的最大值。

• 求所有点对 $u,\ v$ 的 $f(u,\ v)$ 值的平均数。

• $2\leq n\leq 10^5$，$0\leq m,\ a_i\leq 10^5$

解题思路

假设本题给定的是每条边的边权而不是每个点的点权，则对于任意两个点 $u\not=v$，当 $u$ 到 $v$ 的一条路径上的最小边权最大时，易得这条路径在该图的最大生成树上。

如何将点权转化成边权？ 为了转化后等价于点权的情况，对于任意一条路径，路径上点的最小权值必须与路径上边的最小权值。考虑特殊情况，若一条路径上只有一条边，设端点为 $u$ 和 $v$，边权为 $val$，则由上面得到的结论，有 $w=\min(a_u,\ a_v)$。易证路径长度为其他值时也符合条件。

最后考虑答案。分析每条边对答案的贡献。使用并查集，边两边的节点中各选一个点，故贡献为两边集合大小之积再乘上边权所得的值。由于求的是平均数，所以最后记得除以 $\dbinom n2$。

时间复杂度 $\Theta(n+m\log n)$。

AC 代码

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

int n,m,a[100001];
struct Edge{
    int u,v,val;
    inline bool operator<(Edge tmp)const{
        return val>tmp.val;
    }
}edge[100001];

int father[100001],size[100001];
int find(int x){
    if(father[x]!=x)father[x]=find(father[x]);
    return father[x];
}

long long answer;

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",a+i),father[i]=i,size[i]=1;
    for(int i=1;i<=m;i++){
        int x,y; scanf("%d%d",&x,&y);
        edge[i]={x,y,min(a[x],a[y])};
    }
    sort(edge+1,edge+1+m);
    for(int i=1;i<=m;i++){
        int u=find(edge[i].u),v=find(edge[i].v);
        if(u!=v){
            answer+=(long long)edge[i].val*size[u]*size[v];
            father[u]=v,size[v]+=size[u];
        }
    }
    printf("%.4lf\n",answer/(n*(n-1ll)/2.0));
    return 0;
}