题面：

题解：

对边和询问都排序，然后每次把符合当前要求的边都扔并查集里，对于每个询问判断当前并查集里节点数即可。

我很无聊地给并查集加了按秩排序，还开了O2，加了快读，也才170ms，虽然在第一面，然鹅还是没有办法排太前。

上述操作都不做也行

代码：

1 #include
      
        2 #include
       
         3 using namespace std; 4 inline int rd(){ 5     int x=0; char c=getchar(); 6     while(c<'0'||c>'9')c=getchar(); 7     while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();} 8     return x; 9 }10 const int maxn=1e5+5,maxq=1e5+5;11 int N,Q,a,b,c,fa[maxn],dep[maxn],f1,f2,now,cnt[maxn],ans[maxq];12 struct Edge{ int from,to,dis; }edge[maxn];13 struct Query_{ int k,x,id; }qry[maxq];14 inline bool cmp1(const Edge&a,const Edge&b){ return a.dis>b.dis; }15 inline bool cmp2(const Query_&a,const Query_&b){ return a.k>b.k; }16 inline int getf(int a){17     if(fa[a]==a) return a;18     fa[a]=getf(fa[a]);19     return fa[a];20 }21 int main(){22     scanf("%d%d",&N,&Q);23     for(int i=1;i
        
         =qry[i].k){39             now++;40             f1=getf(edge[now].from);41             f2=getf(edge[now].to);42             if(f1!=f2){43                 if(dep[f1]
         
          dep[f2]){48                     fa[f2]=f1;49                     cnt[f1]+=cnt[f2];50                 }51                 else{52                     fa[f1]=f2;53                     dep[f2]++;54                     cnt[f2]+=cnt[f1];55                 }56             }57         }58         ans[qry[i].id]=cnt[getf(qry[i].x)]-1;59     }60     for(int i=1;i<=Q;i++) printf("%d\n",ans[i]);61     return 0;62 }
         
        
       
      

 

---

By:AlenaNuna