TYVJ1460 旅行

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int maxn = 300005;
struct edge{
    int u;
    int v;
    int w;
};
bool judge(edge a,edge b){
    return a.w < b.w;
}
long long n,m,q,k,a[maxn],req[maxn],val[maxn],pa[maxn];
edge g[maxn];
void input(){
    cin>>n>>m>>q;
    for(int i = 1;i <= m;i++){
        scanf("%lld%lld%lld",&g[i].u,&g[i].v,&g[i].w);
    }
    sort(g+1,g+1+m,judge);
    for(int i = 1;i <= n;i++){
        pa[i] = i;
        a[i] = 1;
    }
}
int findf(int x){
    return x != pa[x] ? pa[x] = findf(pa[x]) : x;
}
void init(){
    int fa,fb;
    for(int i = 1;i <= m;i++){
        req[i] = g[i].w;
        fa = findf(g[i].u);
        fb = findf(g[i].v);
        if(fa != fb){
            val[i] = val[i-1] + a[fa] * a[fb];
            a[fb] += a[fa];
            pa[fa] = fb;
        }else{
            val[i] = val[i-1];
        }
    }
}
bool check(int t){
    return k >= req[t];
}
void div(){
    int lans = 0,rans = m,mans;
    while(lans <= rans){
        mans = (lans + rans) >> 1;
        if(check(mans)){
            lans = mans + 1;
        }else{
            rans = mans - 1;
        }
    }
    if(check(mans)) cout<<val[mans]<<endl;
    else cout<<val[mans-1]<<endl;
}
int main(){
    input();
    init();
    for(int i = 1;i <= q;i++){
        scanf("%lld",&k);
        div();
    }
    return 0;
}