题意
给出一个n个点m条边的无向联通图(n,m<=5e5)，有q(q<=5e5)个询问
每个询问询问一个边集{Ei}，回答这些边能否在同一个最小生成树中
分析
要知道一个性质，就是权值不同的边之间是独立的，即权值为x的所有边的选取不影响权值>x的边的选取
于是我们可以把所有询问离线，按边权排序，对于当前处理的边权，如果有某个询问在其中，那么我们把这些边加进去看有没有环，如果有，那么这个询问就被叉掉了，当然处理完了还要把刚才的操作撤销掉
处理了当前权值x的所有询问，最后别忘了把权值为x的边做kruskal算法加进去
这样时间复杂度是带log的（按秩合并的可撤销并查集的复杂度）
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5;
int f[maxn+],sz[maxn+];
int ans[maxn+];
struct Edge
{
int u,v,w;
}edge[maxn+];
vector<int> b[maxn+];
vector<int> q[maxn+];
struct question
{
int id,from,to;
};
vector<question> a[maxn+];
int n,m,Q;
bool cmp(const int x,const int y)
{
return edge[x].w<edge[y].w;
}
stack<pair<int,int> > s;
int find(int x)
{
if(f[x]==x) return x;else return find(f[x]);
}
void Union(int x,int y)
{
if(sz[x]<sz[y]) f[x]=y,sz[y]+=sz[x],s.push(make_pair(x,y));
else f[y]=x,sz[x]+=sz[y],s.push(make_pair(y,x));
}
void remove()
{
pair<int,int> u=s.top();
s.pop();
f[u.first]=u.first;
sz[u.second]-=sz[u.first];
}
bool check(int id,int from,int to)
{
bool ans=;
int sum=;
for(int i=from;i<=to;++i)
{
int p=q[id][i];
int x=find(edge[p].u),y=find(edge[p].v);
if(x!=y) Union(x,y),++sum;else ans=;
}
for(int i=;i<=sum;++i) remove();
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;++i)
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w),b[edge[i].w].push_back(i);
scanf("%d",&Q);
for(int i=;i<=Q;++i)
{
q[i].clear();
int num,x;
scanf("%d",&num);
while(num--)
{
scanf("%d",&x);
q[i].push_back(x);
}
sort(q[i].begin(),q[i].end(),cmp);
int from=;
for(int j=;j<q[i].size();++j)
if(edge[q[i][j]].w!=edge[q[i][j-]].w)
{
a[edge[q[i][j-]].w].push_back({i,from,j-});
from=j;
}
a[edge[q[i][q[i].size()-]].w].push_back({i,from,q[i].size()-});
}
for(int i=;i<=n;++i) f[i]=i,sz[i]=;
for(int i=;i<=maxn;++i)
{
for(int j=;j<a[i].size();++j)
if(!check(a[i][j].id,a[i][j].from,a[i][j].to)) ans[a[i][j].id]=;
for(int j=;j<b[i].size();++j)
{
int p=b[i][j];
int x=find(edge[p].u),y=find(edge[p].v);
if(x!=y) Union(x,y);
}
}
for(int i=;i<=Q;++i)
if(ans[i]) printf("NO\n");else printf("YES\n");
return ;
}