对于所有度数为2的点会使点数减1，边数减1

然而需要特判简单环

我们把询问和边都从大到小排序，然后冰炸鸡维护

Ans_N=n-出度为0的点-出度为2的点+简单环，Ans_M=添加的边数-出度为2的点+简单环

1 #include
      
        2 #include
       
         3 using namespace std; 4 #define mp make_pair 5 #define fir first 6 #define sec second 7 #define maxn 300005 8 struct Road{ 9     int u,v,w;10     bool operator<(Road t)const{ return w>t.w; }11 }R[maxn];12 pair
        
         qry[maxn],ans[maxn];13 int fa[maxn],sz[maxn],er[maxn],du[maxn];14 int n,m,q,zero,two,cir;15 int gf(int x){ return fa[x]=fa[x]==x?x:gf(fa[x]); }16 void un(int x,int y){17     fa[y]=x;18     sz[x]+=sz[y],er[x]+=er[y];19 }20 int add_du(int x){21     int f=gf(x);22     if(du[x]==2){23         if(er[f]==sz[f])cir--;24         two--,er[f]--;25     }26     if(!du[x])zero--;27     du[x]++;28     if(du[x]==2){29         two++,er[f]++;30         if(er[f]==sz[f])cir++;31     }32     return f;33 }34 int main(){35     scanf("%d%d",&n,&m);36     for(int i=1;i<=m;i++)37         scanf("%d%d%d",&R[i].u,&R[i].v,&R[i].w);38     sort(R+1,R+1+m);39     scanf("%d",&q);40     int x;41     for(int i=1;i<=q;i++){42         scanf("%d",&x);43         qry[i]=mp(x,i);44     }45     sort(qry+1,qry+1+q);46     for(int i=1;i<=n;i++)47         sz[i]=1,er[i]=0,fa[i]=i;48     int lst=1;49     zero=n,two=0,cir=0;50     for(int i=q;i;i--){51         for(int j=lst;j<=m&&R[j].w>=qry[i].fir;j++,lst=j){52             int f1=add_du(R[j].u),f2=add_du(R[j].v);53             if(f1!=f2)un(f1,f2); 54         }55         ans[qry[i].sec]=mp((n-zero)-two+cir,(lst-1)-two+cir);56     }57     for(int i=1;i<=q;i++)58         printf("%d %d\n",ans[i].fir,ans[i].sec);59     return 0;60 }