HDU 4750

解题方法，，，首先应该可以看出来是一颗 最小生成树，任意一条的边的价值是不同的；所以计算出最小生成树的每一条边有多少对顶点满足他的 f 值就是这条边的 权值，因此可以在生成最小生成树的时候，进行一下统计，每加入一条边，就统计一下，得到 f 值和这条边权值相同有多少对顶点；方法是  记录一个 rank 数组，记录每个分支里面有多少个顶点，合并的时候，以为 是按照权值从小大大放入的，所以结果是 rank[a]*ran[b]*2; 

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

struct date{
    int u,v,w;
    bool operator < ( const date &a )const{
        return a.w > w;
    }
}edge[1123456];
int N,M,Q;
int f[11234];__int64 rank[11234];
int find( int x ){
    if( x != f[x] )return f[x] = find( f[x] );
    return x;
}
int res[11234];  __int64 num[11234];
int search( int lt,int rt,int key )
{
   if( rt - lt < 4 )
   {
        for( int i = lt; i <= rt; i++ )
        if( res[i] >= key )return i;
        return rt+1;
   }
   int mid = ( lt + rt )>>1;
   if( key > res[mid] )
        return search( mid,rt,key );
   else return search( lt,mid,key );
}
int main( )
{
    int u,v,w;
    while(  scanf("%d%d",&N,&M) != EOF )
    {
        for( __int64 i = 1; i <= M; i++ ){
            scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
        } sort( &edge[1],&edge[1]+M );
        for( int i = 0; i <= N; i++ )f[i] = i;
        for( int i = 0; i <= N; i++ )rank[i] = 1;
        int k = 0;
        for( int i = 1; i <= M; i++ )
        {
            int u = edge[i].u; int v = edge[i].v;
            int a = find( u ); int b = find( v );
            if( a != b )
            {
                res[++k] = edge[i].w;
                num[k] = rank[a]*rank[b]*2;
                rank[b] += rank[a];
                f[a] = b;
            }
        }
        for( int i = k-1; i >= 1; i-- )
            num[i] = num[i]+num[i+1];
        scanf("%d",&Q);
        for( int i = 1; i <= Q; i++ )
        {
           int a; scanf("%d",&a);
           int pos = search( 1,k,a );
           if( pos > k )puts("0");
           else printf("%I64d
",num[pos]);
        }
    }
    return 0;
}