1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 6 int m, n, q; 7 const int maxn = 50005; 8 int fa[maxn]; 9 int Rank[maxn]; 10 11 void init(){ 12 for (int i = 1; i <= n; i++){ 13 Rank[i] = 1; 14 fa[i] = i; 15 } 16 } 17 18 struct node 19 { 20 int u; //路的前端 21 int v; //路的后端 22 int l; //成本 23 }edge[maxn]; 24 25 struct Q 26 { 27 int l, id, ans; 28 }que[maxn]; 29 30 bool cmp(node a, node b){ 31 return a.l < b.l; 32 } 33 34 bool cmp1(Q a, Q b){ 35 return a.l < b.l; //从小到大排序 36 } 37 38 bool cmp2(Q a, Q b){ 39 return a.id < b.id; 40 } 41 42 int find(int x){ 43 if (x == fa[x]) 44 return x; 45 return fa[x] = find(fa[x]); 46 } 47 48 int Set_Union(int x, int y){ 49 int fx = find(x); 50 int fy = find(y); 51 if (fx == fy) 52 return 0; 53 fa[fy] = fx; 54 int t = Rank[fx]; 55 Rank[fx] = Rank[fx] + Rank[fy]; 56 return t*Rank[fy]; 57 } 58 59 int main(){ 60 while (~scanf("%d%d%d", & n, &m, &q)){ 61 init(); 62 que[0].ans = 0; 63 for (int i = 1; i <= m; i++){ 64 scanf("%d%d%d", &edge[i].v, &edge[i].u, &edge[i].l); 65 } 66 for (int i = 1; i <= q; i++){ 67 scanf("%d", &que[i].l); 68 que[i].id = i; 69 que[i].ans = 0; 70 } 71 sort(edge + 1,edge + 1 + m, cmp); 72 sort(que + 1, que + 1 + q, cmp1); 73 int cur = 1; 74 for (int i = 1; i <= q; i++){ 75 que[i].ans = que[i - 1].ans; 76 while (edge[cur].l <= que[i].l&&cur <= m){ 77 que[i].ans += Set_Union(edge[cur].u, edge[cur].v); 78 cur++; 79 } 80 } 81 sort(que + 1, que + 1 + q, cmp2); 82 for (int i = 1; i <= q; i++){ 83 printf("%d\n", que[i].ans); 84 } 85 86 } 87 //system("pause"); 88 return 0; 89 }