传送门：here
简述题意：
给定一张$ n$个点，$ m$条边$ (2<=n,m<=5*10^5)$的无向连通图
有$ k(1<=k<=5*10^5)$次询问
每次询问一个边集$ S(\sum\limits_{i=1}^k|S_i|<=5*10^5)$，判断这些边能否共存于原图的某棵最小生成树上
并查集撤销上一次操作：
不能像普通并查集一样路径压缩，因此只能按址合并
每次把size较小的接到size较大的下面
同时开个栈记录被接上去的点的标号
撤销上一次操作的时候直接把栈顶的标号的father重标成自己同时减小原father的size值即可
题解：
先简化题意：假设每次询问的边集大小均为1
思考克鲁斯卡尔的原理
首先对所有边按边权从小到大排序
克鲁斯卡尔告诉我们一条当前可插入的边权最小的边，插入一定不会不优
因而一条边权为x的边可以在最小生成树内当且仅当把所有权值严格小于x的边插入生成树后加入这条边依然不会形成环
也就是说边权不同的边相互独立，从小到大贪心即可
因此我们把询问离线排序，从小到大判断每次询问对应的边可否插入，可插入则该次询问为YES且插入，否则该次询问一定为NO
如果有两条边边权相同怎么办？
直接检验不一定正确，因为前一条边不一定必选，而之前程序已经将其插入
因此需要撤销上一次并查集的合并操作，然后再检验下一条边
回到原题
我们知道边集大小不一定为1
依然按边权排序，在每条询问边标记询问标号
由于之前提到不同边权相互独立，因此只要某组询问的每一种边权对应的边可以全选，最终也一定可行
反之只要一个询问中有一条边不合法则不可行
因此像上面一样排序后从小到大扫即可
注意同一个询问的相同边权的边检验必须一起做，全部做完之后再一起撤销
因为在同一个询问里同一种边权是不独立的，必须全部插入后依然不形成环才可行
code：
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define rt register int
#define l putchar('\n')
#define ll long long
#define M 1000010
using namespace std;
inline ll read()
{
register ll x = ; char zf = ; char ch;
while (ch != '-' && !isdigit(ch)) ch = getchar();
if (ch == '-') zf = -, ch = getchar();
while (isdigit(ch)) x = x * + ch - '', ch = getchar(); return x * zf;
}
int i,j,k,m,n,x,y,z,cnt,la[M],fa[M],size[M],top,g=;
int ask(int x)
{
while(fa[x]!=x)x=fa[x];
return x;
}
void merge(int x,int y)
{
if(x==y)return;
if(size[x]>size[y])swap(x,y);la[++top]=x;
fa[x]=y;size[y]+=size[x];
}
void undo()
{
int La=la[top];
size[fa[La]]-=size[La];
fa[La]=La;top--;
}
struct ed
{
int x,y,z;
inline bool operator <(const ed s)const
{
return z<s.z;
}
}q[M]; struct query
{
int id,x,y,val;
inline bool operator <(const query s)const
{
if(val==s.val)return id<s.id;
return val<s.val;
}
}A[M];
int ans[M];
int main()
{
n=read();m=read();
for(rt i=;i<=n;i++)size[i]=,fa[i]=i;
for(rt i=;i<=m;i++)
{
x=read();y=read();z=read();
q[i]={x,y,z};
} k=read();
for(rt e=;e<=k;e++)
{
z=read();ans[e]=;
for(rt i=;i<=z;i++)
{
x=read();
A[++cnt]={e,q[x].x,q[x].y,q[x].z};
}
}
sort(q+,q+m+);
sort(A+,A+cnt+);
int qd=;
for(rt i=;i<=cnt;)
{
while(q[qd].z<A[i].val)
merge(ask(q[qd].x),ask(q[qd].y)),qd++; top=;
do
{ int p1=ask(A[i].x),q1=ask(A[i].y);
if(p1==q1)ans[A[i].id]=;
merge(p1,q1);
i++;
}while(A[i].val==A[i-].val&&A[i].id==A[i-].id);
while(top)undo();
}
for(rt i=;i<=k;i++)puts(ans[i]?"YES":"NO");
return ;
}