CodeForces

分析

考虑一个性质：对于一个图的所有 MST，每种边权的边的数量都相等。

因此我们把每种边权的边拿出来单独考虑。我们把并查集恢复到加该种边以前的状态，然后判断这些边加进去会不会成环即可。

现在的问题在于怎么把并查集恢复回去。显然可以可持久化并查集，但是有更优美的做法：预处理出每条边在加该种边权的边时两端点所在的连通块即可。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=500000+10;

int n,m;

struct Edge { int u,v,w,id; } e[N],q[N];
bool operator <(Edge a,Edge b) { return a.w<b.w; }
inline int cmp(Edge a,Edge b) { return a.id<b.id; }

int f[N];
inline void init(int n) { for (re int i=1;i<=n;++i) f[i]=i; }
inline int find(int x) { return x==f[x]?x:f[x]=find(f[x]); }
inline void merge(int a,int b) {
    a=find(a),b=find(b);
    if (a!=b) f[a]=b;
}

int main() {
    n=read(),m=read();
    for (re int i=1;i<=m;++i) e[i]=(Edge){read(),read(),read(),i};
    sort(e+1,e+m+1); init(n);
    for (re int i=1,j=1;i<=m;i=j=j+1) {
        while (j<m&&e[j+1].w<=e[i].w) ++j;
        for (re int k=i;k<=j;++k) e[k].u=find(e[k].u),e[k].v=find(e[k].v);
        for (re int k=i;k<=j;++k) merge(e[k].u,e[k].v);
    }
    sort(e+1,e+m+1,cmp);
    int Q=read();
    while (Q--) {
        int s=read(),flag=1;
        for (re int i=1;i<=s;++i) q[i]=e[read()];
        sort(q+1,q+s+1);
        for (re int i=1,j=1;i<=s;i=j=j+1) {
            while (j<s&&q[j+1].w<=q[i].w) ++j;
            for (re int k=i;k<=j;++k) f[q[k].u]=q[k].u,f[q[k].v]=q[k].v;
            for (re int k=i;k<=j;++k) {
                if (find(q[k].u)==find(q[k].v)) { flag=0; break; }
                else merge(q[k].u,q[k].v);
            }
            if (!flag) break;
        }
        if (flag) puts("YES");
        else puts("NO");
    }
    return 0;
}