记录编号	58237	评测结果	AAAAAAAAAA
题目名称	威尼斯旅行	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	2.892 s
提交时间	2013-04-18 18:34:06	内存使用	6.05 MiB

#include<iostream>
#include<cstdio>
#include<deque>
#include<algorithm>
using namespace std;
const int SIZEN=100001,SIZEM=200001,SIZEQ=200001;
int n,m,q;
long long k;
class SIDE{
public:
	int x,y;//端点
	long long w;//权值
}c[SIZEM];
bool operator < (SIDE a,SIDE b){
	return a.w<b.w;
}
int father[SIZEN]={0};
long long size[SIZEN]={0};
int tot=1;
void clear(void){
	int i;
	for(i=1;i<=n;i++) father[i]=-1,size[i]=1;
}
int grand(int x){
	if(father[x]==-1) return x;
	else{
		father[x]=grand(father[x]);
		return father[x];
	}
}
void merger(int a,int b){
	if(size[a]<size[b]){
		father[a]=b;
		size[b]+=size[a],size[a]=0;
	}
	else{
		father[b]=a;
		size[a]+=size[b],size[b]=0;
	}
}
#define now c[tot]
long long ans[SIZEQ]={0};
int reque[SIZEQ]={0};
int lis[SIZEQ]={0};
long long nowans=0;
bool cmp(int a,int b){
	return reque[a]<reque[b];
}
void deal(int s){
	int temp1,temp2;
	while(tot<=m&&now.w<=reque[s]){
		temp1=grand(now.x),temp2=grand(now.y);
		if(temp1!=temp2){
			nowans+=(size[temp1]*size[temp2]);
			merger(temp1,temp2);
		}
		tot++;
	}
	ans[s]=nowans;
}
void work(void){
	scanf("%d%d%d",&n,&m,&q);
	int i;
	int x,y,w;
	for(i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&w);
		c[i].x=x,c[i].y=y,c[i].w=w;
	}
	sort(c+1,c+1+m);
	tot=1;
	clear();
	for(i=1;i<=q;i++){
		lis[i]=i;
		scanf("%d",&reque[i]);
	}
	sort(lis+1,lis+1+q,cmp);
	for(i=1;i<=q;i++){
		deal(lis[i]);
	}
	for(i=1;i<=q;i++) cout<<ans[i]<<endl;
}
int main(){
	freopen("tripa.in","r",stdin);
	freopen("tripa.out","w",stdout);
	work();
	return 0;
}