按边从小到大排序。
对于每条边(from, to, dist)，如果from和to在同一个集合中，那么这条边无意义，因为之前肯定有比它更小的边连接了from和to。
如果from和to不属于同一个集合，那么增加这条边后增加的点对数目是cnt[from]*cnt[to]*2（ 因为(u, v)和(v, u)不算同一点对，所以*2 ）
统计出所有点对数total。
对于查询，按t值从小到大排序，边从小到大一条一条往里加。
tmpSum为f值小于t的点对总数。
当边权大于等于t值时：ans[i] = total - tmpSum。
当边权小于t值时，更新tmpSum。
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm> #define LL long long int using namespace std; const int MAXN = ; struct node
{
int from, to, dist;
bool friend operator<( node lhs, node rhs )
{
return lhs.dist < rhs.dist;
}
}; struct Query
{
int id;
LL t;
bool friend operator<( Query lhs, Query rhs )
{
return lhs.t < rhs.t;
}
}; node D[MAXN*];
int N, M;
LL ans[MAXN*];
Query qry[MAXN*]; int p[MAXN];
LL cnt[MAXN]; int find( int x )
{
return p[x] == x ? x : p[x] = find(p[x]);
} void init()
{
for ( int i = ; i <= N; ++i )
{
p[i] = i;
cnt[i] = ;
}
return;
} int main()
{
while ( scanf( "%d%d", &N, &M ) == )
{
init();
for ( int i = ; i < M; ++i )
{
scanf("%d%d%d", &D[i].from, &D[i].to, &D[i].dist );
int x = find( D[i].from );
int y = find( D[i].to );
if ( x != y )
{
p[y] = x;
cnt[x] += cnt[y];
}
} LL total = ;//统计所有点对
for ( int i = ; i < N; ++i )
{
if ( p[i] == i )
total += ( cnt[i]*( cnt[i] - ) );
} sort( D, D + M );
int Q;
scanf( "%d", &Q );
for ( int i = ; i < Q; ++i )
{
scanf( "%I64d", &qry[i].t );
qry[i].id = i;
}
sort( qry, qry + Q ); init();
int i = , j = ;
LL tmpSum = ;
while ( j < Q )
{
//printf( "tot=%I64d tmp=%I64d\n", total, tmpSum );
if ( i < M && qry[j].t <= D[i].dist )
{
int id = qry[j].id;
ans[id] = total - tmpSum;
++j;
}
else if ( i < M )
{
int x = find( D[i].from );
int y = find( D[i].to );
if ( x != y )
{
p[y] = x;
tmpSum += cnt[x]*cnt[y]*;
cnt[x] += cnt[y];
}
++i;
}
else if ( i >= M )
{
ans[ qry[j].id ] = total - tmpSum;
++j;
}
} for ( int i = ; i < Q; ++i )
printf( "%I64d\n", ans[i] );
}
return ;
}