【JZOJ A组】旅游

Description

Input

Output

Sample Input

1
5 5 3
2 3 6334
1 5 15724
3 5 5705
4 3 12382
1 3 21726
6000
10000
13000

Sample Output

2
6
12

Data Constraint

思路

排序+并查集

给边长短排序和询问排序，每加上一条边，相当于合并两个集合

统计答案显然

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=1e5+77;
int t,n,m,q,f[maxn],size[maxn];
ll ans=0;
struct A
{
	int x,y,v;
}a[maxn];
int gf(int x)
{
	return x==f[x]?x:f[x]=gf(f[x]);
}
struct B
{
	int x,id;
	ll ans;
}b[maxn];
bool cmp1(A x,A y)
{
	return x.v<y.v;
}
bool cmp2(B x,B y)
{
	return x.x<y.x;
}
bool cmp3(B x,B y)
{
	return x.id<y.id;
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d%d",&n,&m,&q);
		for(int i=1; i<=n; i++) f[i]=i,size[i]=1;
		ans=0;
		for(int i=1; i<=m; i++)
		{
			scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].v);
		}
		sort(a+1,a+m+1,cmp1);
		for(int i=1; i<=q; i++)
		{
			scanf("%d",&b[i].x); b[i].id=i;
		}
		sort(b+1,b+q+1,cmp2);
		int p=1;
		for(int i=1; i<=q; i++)
		{
			while(a[p].v<=b[i].x)
			{
				int u=gf(a[p].x),v=gf(a[p].y);
				if(u!=v) f[u]=v,ans+=size[u]*size[v],size[v]+=size[u];
				p++;
			}
			b[i].ans=ans;
		}
		sort(b+1,b+q+1,cmp3);
		for(int i=1; i<=q; i++) printf("%lld\n",b[i].ans*2);
	}
}