题目描述
小明很想出去走走。但是小明讨厌太拥挤的地方，她会拒绝一些人气旺盛的道路。有 个景点，有 双向道路。每条道路有一个人气值 ，表示这条道路的拥挤程度。小明不会经过那些人气值大于 的道路，他想知道有多少对景点 使得从 景点出发可以到达 景点。
输入格式
第一行一个整数 ，表示有 组数据。
对于每组数据，第一行有三个数 ， 表示有 组询问。
接下来 行，每行三个数 ，表示有一条连接 ，人气值为 的道路。
最后 行，每行一个整数 ，代表询问。
输出格式
对于每组数据，输出 行，依次回答所有询问。
样例
样例输入
1
5 5 3
2 3 6334
1 5 15724
3 5 5705
4 3 12382
1 3 21726
6000
10000
13000
样例输出
2
6
12
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e4+10;
int T,fa[MAXN],cnt[MAXN];
inline int find(int x){
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
inline merge(int x,int y){
int fax=find(x),fay=find(y);
fa[fax]=fay;
}
struct nod1{
int x,y,d;
}edges[MAXN*5];
inline int cmp1(nod1 a,nod1 b){
return a.d<b.d;
}
struct nod2{
int id,x;
}query[MAXN*5];
inline int cmp2(nod2 a,nod2 b){
return a.x<b.x;
}
int main() {
cin>>T;
while(T--){
int n,m,q;cin>>n>>m>>q;
for (int i=1;i<=n;i++) cnt[i]=1,fa[i]=i;
for (int i=1;i<=m;i++) cin>>edges[i].x>>edges[i].y>>edges[i].d;
sort(edges+1,edges+1+m,cmp1);
for (int i=1;i<=q;i++) cin>>query[i].x,query[i].id=i;
sort(query+1,query+1+q,cmp2);
}
return 0;
}