City
https://codeforces.com/gym/103145/problem/K
题意：
由m条无向道路连接的n个城市，每条道路都有一个强度ki。敌人将进攻摧毁这些道路。当敌人发动伤害为x的攻击时，所有力量小于x的道路都将被摧毁。现在有Q个问题要问你，如果敌人发动伤害为pi的攻击，有多少对城市可以到达。城市x和城市y是可到达的，这意味着有一条从x到y的路径，并且该路径中每条道路的强度大于或等于pi。
题解：贪心+并查集
对于每个询问，我们可以看做每次把大于等于qi的路添加进去；
我们可以按照每条路的强度从大到小排序，q个询问也按照pi从大到小排序，这样既可以去掉重复的pi多次查询，也贪心去添加大于pi的路；然后每次添加路的时候，再使用并查集，就知道u,v是否已经在一个集合中，
如果在一个集合中，就不需要操作了；反之则需要把u,v添加到相同集合中；
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
ll a[N],mp[N],n,m,q,ans[N],cnt,sum[N];//ans存储每次查询的对数，sum存储当前点为父节点的点数;
struct node{
ll u,v;
ll w;
bool operator <(const node &t){//每条路的强度从大到小排序
return w>t.w;
}
}edge[4*N];
struct node1{
ll id;
ll p;
bool operator <(const node1 &t){//q个询问也按照pi从大到小排序
return p>t.p;
}
}nd[2*N];
void creat(){//初始并查集
for(ll i=1;i<=n;i++){
a[i]=i;
sum[i]=1;
ans[i]=0;
}
}
int find(int x) {
if(x!=a[x]) a[x]=find(a[x]);
return a[x];
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--){
cin>>n>>m>>q;
creat();
cnt=0;
nd[0].p=0,nd[0].id=0;
for(int i=1;i<=m;i++){
ll u,v,w;
cin>>u>>v>>w;
edge[++cnt]={u,v,w};
}
sort(edge+1,edge+1+cnt);
for(int i=1;i<=q;i++){
cin>>nd[i].p;
nd[i].id=i;
}
sort(nd+1,nd+1+q);
int j=1;
for(int i=1;i<=q;i++){
ll ans1=0;
ans1=ans[nd[i-1].id];
for(;j<=cnt;j++){
if(edge[j].w<nd[i].p) break;//如果比当前查询的的要小就退出
ll u,v,w;
u=edge[j].u;
v=edge[j].v;
w=edge[j].w;
ll k1,k2;
k1=find(u);
k2=find(v);
if(a[k1]!=a[k2]){//需要合并
ans1=ans1-(sum[a[k1]]*(sum[a[k1]]-1)/2+sum[a[k2]]*(sum[a[k2]]-1)/2);//减去原来的a[k1]的对数和原来的a[k2]的对数
sum[a[k1]]+=sum[a[k2]];//把集合a[k2]的点数加入到a[k1];
ans1+=sum[a[k1]]*(sum[a[k1]]-1)/2;//把新的a[k1]的对数重新计算加入
sum[a[k2]]=0;//把集合a[k2]变为0;
a[k2]=a[k1];//合并
}
}
ans[nd[i].id]=ans1;
}
for(int i=1;i<=q;i++){
cout<<ans[i]<<endl;//输出每次查询
}
}
return 0;
}