hdu 5441 Travel 離線操作+并查集

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = ;
const int INF  = ;
int pre[MAXN<<];
int M,N;

struct Node{
    int a,b,val;
}e[MAXN<<];
bool cmp(Node a,Node b)
{
    return a.val<b.val;
}
struct Node2{
    int bre,id;
}s[MAXN];
bool cmp2(Node2 a,Node2 b)
{
    return a.bre<b.bre;
}
int w[MAXN<<];
int findSet(int x)
{
    return (x==pre[x])?pre[x]:(pre[x] = findSet(pre[x]));
}
int main()
{
    int T,Q;
    scanf("%d",&T);
    while(T--)
    {
        int ans[MAXN];
        scanf("%d%d%d",&N,&M,&Q);
        for(int i=;i<=N;i++)
            pre[i] = i,w[i] = ;
        for(int i=;i<=M;i++)
            scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].val);
        sort(e+,e+M+,cmp);
        for(int i=;i<=Q;i++)
            scanf("%d",&s[i].bre),s[i].id = i;
        sort(s+,s+Q+,cmp2);
        int amount = ,j = ;
        for(int i=;i<=Q;i++)
        {
            for(;j<M&&e[j].val<=s[i].bre;j++)
            {
                int fx = findSet(e[j].a),fy = findSet(e[j].b);
                if(fx!=fy)
                {
                    pre[fx] = fy;
                    amount -= (w[fx]*(w[fx]-) + w[fy]*(w[fy]-));
                    w[fy] += w[fx];
                    amount += w[fy]*(w[fy]-);
                }
            }
            ans[s[i].id] = amount;
        }
        for(int i=;i<=Q;i++)
            printf("%d\n",ans[i]);
    }
    return ;
}