传送门：点击打开链接
题意：给n个点，m条有权值的无向边，求存在多少个点(a,b) (a!=b)，使得a到b至少有一条路径上的边最大权值小于等于x
思路：将边读入排序，再先将x排序，初始化并查集，用并查集维护一个联通分量中的点的个数，让ans等于0
按照边的权值从小到大添加边到图中，首先考虑如何更新ans
添加的某条边如果是(u,v)，如果u和v本身就连通了，那么再添加这条边并不会改变ans
如果u和v没有连通，假设u所在连通分量的点个数是n1,v所在的连通分量的点个数是n2
对于第一个连通分量，合并后这个连通分量就不存在了，ans会减少n1*(n1-1)对点
对于第二个连通分量，合并后这个连通分量就不存在了，ans会减少n2*(n2-1)对点
合并后，多了一个合并的连通分量，ans会增加(n1+n2)*(n1+n2-1)对点
更新的时候顺便看边的权值和x[cur]的大小关系，当权值大于x[cur]的时候就更新此时x的答案，因为在添加这条边之前的所有的边的权值都是小于等于x[cur]的，说明之前形成的所有点对就是此时的答案，保存好就行
#include<map>
#include<set>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define fuck printf("fuck")
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w+",stdout)
using namespace std;
typedef long long LL;const int MX = 100000 + 5;struct Edge {int u, v, cost;bool operator<(const Edge &b) const {return cost < b.cost;}
} E[MX];struct Que {int id, x;bool operator<(const Que &b)const {return x < b.x;}
} Q[MX];LL ans[MX];
int P[MX], num[MX];int find(int x) {return P[x] == x ? x : (P[x] = find(P[x]));
}int main() {int T; //FIN;scanf("%d", &T);while(T--) {int n, m, q;scanf("%d%d%d", &n, &m, &q);for(int i = 1; i <= n; i++) {P[i] = i;num[i] = 1;}for(int i = 1; i <= m; i++) {scanf("%d%d%d", &E[i].u, &E[i].v, &E[i].cost);}sort(E + 1, E + 1 + m);for(int i = 1; i <= q; i++) {Q[i].id = i;scanf("%d", &Q[i].x);}sort(Q + 1, Q + 1 + q);int cur = 1; LL s = 0;for(int i = 1; i <= m; i++) {while(cur <= q && E[i].cost > Q[cur].x) {ans[Q[cur++].id] = s;}int p1 = find(E[i].u), p2 = find(E[i].v);if(p1 != p2) {LL n1 = num[p1], n2 = num[p2];s = s - n1 * (n1 - 1) - n2 * (n2 - 1) + (n1 + n2) * (n1 + n2 - 1);P[p1] = p2;num[p2] += num[p1];}}while(cur <= q) {ans[Q[cur++].id] = s;}for(int i = 1; i <= q; i++) {printf("%I64d\n", ans[i]);}}return 0;
}