CF891C Envy

Link
需要注意到Kruskal算法的一些性质。
(1.)一个图所有可能的最小生成树中某个权值的边的个数是相等的。
(2.)当我们把所有边权(le w)的边加入生成树之后，所有情况下这个图的连通性都一样。
因此我们可以把一个询问拆成每种边权的边是否能有给定数目条同时在一个生成树内。
我们还是做Kruskal的过程，途中检查就行了。
注意需要可撤销的并查集。

#include<bits/stdc++.h>
using namespace std;
namespace IO
{
    char ibuf[(1<<21)+1],*iS,*iT;
    char Get() { return (iS==iT? (iT=(iS=ibuf)+fread(ibuf,1,(1<<21)+1,stdin),(iS==iT? EOF:*iS++)):*iS++); }
    int read(){int x=0;char ch=Get();while(ch>57||ch<48)ch=Get();while(ch>=48&&ch<=57)x=x*10+(ch^48),ch=Get();return x;}
}
using namespace IO;
const int N=500007;
int max(int a,int b){return a>b? a:b;}
int min(int a,int b){return a<b? a:b;}
void swap(int &a,int &b){a^=b^=a^=b;}
struct edge{int u,v,w;}e[N];
struct query{int id,u,v,w;};vector<query>q[N];
int fa[N],size[N],ans[N];stack<int>stk;
int Find(int x){while(fa[x]^x)x=fa[x];return x;}
int merge(int x,int y)
{
    int u=Find(x),v=Find(y);
    if(u==v) return 0;
    if(size[u]>size[v]) swap(u,v);
    fa[u]=v,size[v]+=size[u],stk.push(u);
    return 1;
}
int main()
{
    int i,j,k,n=read(),m=read(),Q,w,x;
    for(i=1;i<=m;++i) e[i]=(edge){read(),read(),read()};
    for(Q=read(),i=1;i<=Q;++i) for(k=read(),j=1;j<=k;++j) x=read(),q[e[x].w].push_back((query){i,e[x].u,e[x].v,e[x].w});
    for(i=1;i<=n;++i) fa[i]=i,size[i]=1;
    for(i=1;i<=Q;++i) ans[i]=1;
    sort(e+1,e+m+1,[](edge a,edge b){return a.w<b.w;});
    for(i=1;i<=m;++i)
    {
	while(!stk.empty())stk.pop();
	for(j=0;j<q[w=e[i].w].size();++j)
	{
	    if(!ans[q[w][j].id]) continue;
	    if(j>0&&q[w][j].id^q[w][j-1].id) while(!stk.empty()) x=stk.top(),stk.pop(),size[fa[x]]-=size[x],fa[x]=x;
	    if(!merge(q[w][j].u,q[w][j].v)) ans[q[w][j].id]=0;
	}
	while(e[i].w==w) merge(e[i].u,e[i].v),++i;
	if(e[i].w^w) --i;
    }
    for(i=1;i<=Q;++i) puts(ans[i]? "YES":"NO");
}