题意：给n个节点m条带权值边的无向图。然后q个问题，每次询问点对的数目，点对需要满足的条件是：1）连通；2）其路径的最大权值不能超过询问值。
分析：如果没次询问一次，dfs一次，很可能超时，因此可以用并查集。离线处理，把边按权值排序，把问题按大小排序。然后离线的过程就是不断向图中加边的过程。
比如样例如下：
然后离线处理，排完序后将会是一条一条的加边：问题也排了序，因此是个累加过程。。。
#include <cstdio>
#include <iostream>
#include <sstream>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#define ll long long
#define mem(m, a) memset(m, a, sizeof(m))
#define repu(i, a, b) for(int i = a; i < b; i++)
#define maxn 100005
const double PI=-acos(-1.0);
using namespace std;
struct node
{
int x,y,z;
bool operator < (const node &a) const
{
return z < a.z;
}
} e[maxn];
struct Q
{
int w,id;
bool operator < (const Q &a) const
{
return w < a.w;
}
} q[maxn];
int ans[maxn];
int fa[maxn],num[maxn];
int find_set(int x)
{
if(x==fa[x])
return fa[x];
else
return fa[x]=find_set(fa[x]);
}
int main()
{
int n,m,k,t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&n,&m,&k);
repu(i,,m)
scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z);
repu(i,,k)
scanf("%d",&q[i].w),q[i].id=i;
sort(e,e+m);
sort(q,q+k);
repu(i,,+n)
fa[i]=i,num[i]=;
int cnt=,j=;
repu(i,,k)
{
while(j<m&&e[j].z<=q[i].w)
{
int x=find_set(e[j].x);
int y=find_set(e[j].y);///找各自的所属的集合编号
if(x != y)
{
cnt += num[x]*num[y];///各自集合的数目相乘
fa[x] = y;///因为已经统一集合了
num[y] += num[x];///y集合的数目就可以直接加上x的数目
}
j++;
}
ans[q[i].id] = *cnt;
}
repu(i,,k)
printf("%d\n",ans[i]);
}
return ;
}