毕业了，Xth很高兴，因为他要和他的 rabbit 去双人旅行了。他们来到了水城威尼
斯。众所周知（⊙﹏⊙b汗），这里的水路交通很发达，所以 xth 和 rabbit 只好坐
船穿梭于各个景点之间。但是要知道，rabbit 是会晕船的，看到她难受，xth 是会
心疼的。
已知城市中有n个景点，这些景点之间有m条双向水路，在每条水路上航行时
rabbit 都会有一个“晕船值”。旅行时，xth 会带着 rabbit 尽量选择晕船值小的路线
旅行。但是 rabbit 也是有一定忍耐限度度的，如果晕船值超过了她的忍耐度，xth
会果断决定放弃这条路线。
现在 xth 想进行若干次询问，给定 rabbit 的忍耐度，问还有多少对城市(x,y)间会存
在可行的旅行路线（如果(x,z)和(z, y)可行，则(x,y)可行，也就是说连通性是可传
递的）。
第 1 行三个正整数n、m、q，分别表示景点数量、水路数量和询问次数。
第 2 行到第m + 1行每行三个正整数x、y、w，表示x号景点和y号景点之间有一条
“晕船值”为w的双向水路。
第m + 2行至第m + q + 1行，每行一个正整数k，表示询问中给定的 rabbi忍耐度
为k。
共q行，对于每次询问做出回答。
5 5 2
1 2 1
2 3 2
3 4 1
4 5 4
5 1 1
1
2
4
10
第一个询问：(1,2), (1,5), (2,5), (3,4)。其中(2,5)的具体走法为：2 − 1 − 5
第二个询问：(1,2), (1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (3,4), (3,5), (4,5)。其中(4,5)
的具体走法为：4 − 3 − 2 − 1 − 5
对于20%的数据满足n ≤ 20,m ≤ 40,q ≤ 40；
对于40%的数据满足n ≤ 1000,m ≤ 2000,q ≤ 1000；
对于60%的数据满足n ≤ 3000,m ≤ 6000,q ≤ 200000；
对于100%的数据满足n ≤ 100000,m ≤ 200000,q ≤ 200000。其他数不超过10^9.
/* 刚开始把范围看成10了，以为是个水题，然后就打脸了。 离线处理出范围，然后每增加一定的范围，就做一部分的最小生成树，更新答案。处理一个c表示当前这个连通块的节点数量，如果a，b连接，增加的答案为c[a]*c[b]。 */ #include<cstdio> #include<iostream> #include<algorithm> #define N 100010 #define lon long long using namespace std; int fa[N],c[N],n,m,q,maxw,minw=N; lon sum[11]; struct node{ int u,v,t; };node e[N*2]; struct Node{ int num,limit;lon ans; };Node qu[N*2]; bool cmp1(const node&s1,const node&s2){ return s1.t<s2.t; } bool cmp2(const Node&s1,const Node&s2){ return s1.limit<s2.limit; } bool cmp3(const Node&s1,const Node&s2){ return s1.num<s2.num; } int find(int x){ if(fa[x]==x)return x; return fa[x]=find(fa[x]); } int main(){ freopen("jh.in","r",stdin); scanf("%d%d%d",&n,&m,&q); for(int i=1;i<=m;i++){ scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].t); maxw=max(maxw,e[i].t); minw=min(minw,e[i].t); } for(int i=1;i<=q;i++){ scanf("%d",&qu[i].limit); qu[i].num=i; } sort(e+1,e+m+1,cmp1); sort(qu+1,qu+q+1,cmp2); for(int i=1;i<=n;i++)fa[i]=i,c[i]=1; int epos=1;lon tot=0; for(int i=1;i<=q;i++){ if(qu[i].limit==qu[i-1].limit){ qu[i].ans=qu[i-1].ans; continue; } for(int j=epos;j<=m&&e[j].t<=qu[i].limit;j++){ int a=find(e[j].u); int b=find(e[j].v); if(fa[a]!=b){ fa[a]=b; tot+=c[a]*c[b]; c[b]+=c[a];c[a]=0; } epos=j+1; } qu[i].ans=tot; } sort(qu+1,qu+q+1,cmp3); for(int i=1;i<=q;i++){ printf("%lld ",qu[i].ans); } return 0; }