二分边，要把边最小值尽可能最大化，可以对这个值进行二分判断是否可以，在判断的过程中，如果是要连接的次数等于n-1，n为点的数量，点之间如果要构成生成树最少连接的数量为n-1，所以说判断的时候可以通过连接的次数来判断是否可以构成生成树
将 最小生成树 的那条边进行最小值的最大化之后，就可以再往后遍历的过程中，把要用到的n-1条边进行记录下来，然后进行下一步操作->计算边权
将要用到的边记录下来之后，按照边权的大小对他进行从大到小进行排序，用并查集来维护两个联通块的大小，这个联通块对答案的贡献就是两个联通块的大小size_a * size_b * w
两个联通块的大小最后于边权相乘就是这个联通块对答案的贡献
关于在计算贡献的时候为什么要将边权按照从大到小的顺序进行排列？下面讨论两种情况：
从大到小排序之后，刚开始有两个点->a,b，这两个点之间为大边权，那么这两个点之间的贡献那就是siz_a * siz_b * w_big
如果再有另外的点a1,a2,a3连到a上，另外的点b1,b2,b3连到b上，那么之前算的贡献不会影响，其余后来的点之间的边权一定是比w_big要小，就是路径上的最小权值，不会对答案产生影响
从小到大排序之后，刚开始有两个点->a,b，这两个点之间的小边权，那么这两个点之间的贡献那就是siz_a * siz_b * w_little
如果再有另外的点a1,a2,a3连到a上，另外的点b1,b2,b3连到b上，就会少算一部分贡献因为最后乘的数都是小边权
ll n,m; ll cnt; ll res; itn head[maxn]; ll fa[maxn]; ll dis[maxn]; ll siz[maxn]; int find(int x){ if(x == fa[x]) return x; else return fa[x] = find(fa[x]); } struct edg{ int u; itn v; ll w; }a[maxn],edge[maxn]; bool cmp(edg aa,edg bb){ return aa.w < bb.w; } bool cp(edg aa,edg bb){ return aa.w > bb.w; } int t = 0; bool judge(int x){ if(m-x+1 < n-1) return false; int tot = 0; for(itn i=1;i<=n;i++) fa[i] = i; for(int i=x;i<=m;i++){ int uu = a[i].u; int vv = a[i].v; ll ww = a[i].w; int fauu = find(uu); int favv = find(vv); if(fauu != favv) fa[fauu] = favv,tot ++;/// eq n-1 } if(tot == n-1) return true; return false; } int main() { cin >>n >> m; for(int i=0;i<=n;i++){ fa[i] = i; siz[i] = 1; head[i] = -1; } for(itn i=1;i<=m;i++){ a[i].u = read; a[i].v = read; a[i].w = read; } sort(a+1,a+1+m,cmp); /// puts("1 ok "); int le = 1; int ri = m; int pos; while(le < ri){ int md = (le + ri) >> 1; if(judge(md)) le = md+1,pos = md; else ri = md; } for(int i=1;i<=n;i++) siz[i] = 1; for(int i = 1;i <= n;i ++) fa[i] = i; for(int i=pos;i<=m;i++){ int uu = a[i].u; int vv = a[i].v; int ww = a[i].w; int fauu = find(uu); int favv = find(vv); ///printf("uu: %d vv: %d fauu: %d favv: %d\n",uu,vv,fauu,favv); if(fauu == favv) continue; ++ t; fa[fauu] = favv; edge[t].u = uu; edge[t].v = vv; edge[t].w = ww; if(t == n - 1) break; } ///printf("t: %d\n",t); ll ans = 0; sort(edge+1,edge+1+t,cp); for(int i=1;i<=n;i++) fa[i] = i,siz[i] = 1; for(int i=1;i<=t;i++){ int uu = edge[i].u; int vv = edge[i].v; int ww = edge[i].w; int fauu = find(uu); int favv = find(vv); if(fauu == favv) continue; else{ fa[fauu] = favv; ans += ww * siz[fauu] * siz[favv]; siz[favv] += siz[fauu]; } } cout << ans <<endl; return 0; }
