[USACO18JAN] MooTube (离线并查集)

题目大意：给你一棵边权树，定义两点间距离为它们唯一路径上的最小路权，求与某点距离不大于K(k为已知)的点的数量

带权并查集维护集合内元素总数

路和问题 都按权值大到小排序，枚举问题， 建权值不小于K的边，并查集维护连通性，求集合元素内总数即可

 #include <bits/stdc++.h>

 #define N 200100

 #define inf 0x3f3f3f3f

 using namespace std;

 int n,q,cnt;

 int fa[N],f[N];

 struct EDGE{

     int x,y,w;

 }edge[N];

 struct QUES{

     int k,v,id,ans;

 }ques[N];

 int cmp1(EDGE s1,EDGE s2) {return s1.w>s2.w;}

 int cmp2(QUES s1,QUES s2) {return s1.k>s2.k;}

 int cmp3(QUES s1,QUES s2) {return s1.id<s2.id;}

 void edge_add(int x,int y,int z)

 {

     cnt++;

     edge[cnt].x=x;

     edge[cnt].y=y;

     edge[cnt].w=z;

 }

 int find_fa(int x)

 {

     int fx=x;

     while(fx!=fa[fx]) {fx=fa[fx];}

     while(fa[x]!=fx)

     {

         int pr=fa[x];

         f[pr]-=f[x];

         fa[x]=fx;

         x=pr;

     }

     return fx;

 }

 void comb(int x,int y)

 {

     int fx=find_fa(x);

     int fy=find_fa(y);

     fa[fy]=fx;

     f[fx]+=f[fy];

 }

 int main()

 {

     scanf("%d%d",&n,&q);

     for(int i=;i<n;i++)

     {

         int x,y,z;

         scanf("%d%d%d",&x,&y,&z);

         edge_add(x,y,z);

     }

     sort(edge+,edge+n,cmp1);

     for(int i=;i<=q;i++)

     {

         int x,y;

         scanf("%d%d",&x,&y);

         ques[i].k=x;

         ques[i].v=y;

         ques[i].id=i;

     }

     sort(ques+,ques+q+,cmp2);

     for(int i=;i<=n;i++)

     {

         fa[i]=i;

         f[i]=;

     }

     int j=;

     for(int i=;i<=q;i++)

     {

         while(edge[j].w>=ques[i].k)

         {

             comb(edge[j].x,edge[j].y);

             j++;

         }

         int fv=find_fa(ques[i].v);

         ques[i].ans=f[fv]-;

     }

     sort(ques+,ques+q+,cmp3);

     for(int i=;i<=q;i++)

     {

         printf("%d\n",ques[i].ans);

     }

     return ;

 }