题目描述

$A$国有$n$座城市,每座城市都十分美,这使得A国的民众们非常喜欢旅行。

然而,$A$国的交通十分落后,这里只有$m$条双向的道路,并且这些道路都十分崎岖,有的甚至还是山路,只能靠步行。

通过每条道路的长度、泥泞程度等因素,我们给每条道路评估一个“崎岖度”,表示通过这条道路的不舒适程度。

从$X$城市经过若干条道路到达$Y$城市,我们称这次旅行的“代价”为所经过道路“崎岖度”的最大值。

当然,如果从$X$城市到$Y$城市有多条路线,民众们会自觉选择“代价”最小的路线进行旅行。

但是,如果旅行的“代价”超过了他们的“忍耐度”,他们就不选择这个旅行了,甚至宁愿在家里宅着。

现在$A$国的国王想进行若干次询问:给定民众的“忍耐度”,问还有多少对城市$(X,Y)$会存在旅行?

请你对国王的每次询问分别给出回答。

输入格式

第$1$行三个正整数$n、m、Q$,分别表示城市数量、道路数量和询问次数。
第$2$行到第$m+1$行每行三个正整数$x、y、w$,表示$x$号城市和$y$号城市之间有一条“崎岖度”为$w$的双向道路。
第$m+2$行至第$m+Q+1$行,每行一个正整数$k$,表示询问中给定的“忍耐度”为$k$。

输出格式

共$Q$行,对于每次询问做出回答。

样例输入

5 5 2
1 2 1
2 3 2
3 4 1
4 5 4
5 1 1
1
2

样例输出

4
10

数据范围

$n<=100000,m<=200000,Q<=200000$,其他数不超过$10^9$。

菜鸡的咆哮

考虑离线处理。

将道路信息与询问按崎岖度/忍耐度从小到大排序。

可以确保处理第$i$个疑问时,崎岖度$\leq$第$i-1$个询问忍耐度的边已全部加入。

对于每一个询问,用并查集维护联通块。

在加边合并两个$size$为$p$和$q$的联通块时,$ans+=p\times q$。

代码

#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
int n,m,t;
struct data{
    int a,b,w;
}line[2*maxn];
bool cmp(data x,data y){
    return x.w<y.w;
}
struct ask{
    int q,pos,ans;
}xx[2*maxn];
bool cmpq(ask a,ask b){
    return a.q<b.q;
}
bool cmpp(ask a,ask b){
    return a.pos<b.pos;
}
int fa[maxn],size[maxn];
int dofind(int x){
    if(fa[x]==x) return x;
    return fa[x]=dofind(fa[x]);
}
void dounion(int x,int y){
    size[dofind(y)]+=size[dofind(x)]; 
    fa[dofind(x)]=dofind(y);
}
int main(){
    scanf("%d%d%d",&n,&m,&t);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&line[i].a,&line[i].b,&line[i].w);
    }
    sort(line+1,line+1+m,cmp);
    for(int i=1;i<=t;i++){
        scanf("%d",&xx[i].q);
        xx[i].pos=i;
    }
    sort(xx+1,xx+1+t,cmpq);
    for(int i=1;i<=n;i++) fa[i]=i,size[i]=1;
    int sign=1,ans=0;
    for(int i=1;i<=t;i++){
        while(sign<=m&&line[sign].w<=xx[i].q){
            int x=line[sign].a;
            int y=line[sign].b;
            if(dofind(x)!=dofind(y)){
                ans+=size[dofind(x)]*size[dofind(y)];
                dounion(x,y); 
            }
            sign++;
        }
        xx[i].ans=ans; 
    }
    sort(xx+1,xx+1+t,cmpp);
    for(int i=1;i<=t;i++){
        printf("%d\n",xx[i].ans);
    }
    return 0;
}