题目链接：http://codeforces.com/contest/891/problem/C
题目大意：给你n个点m条边的无向图。给你q个询问：
每个询问给出一些边集。问你这些边集可不可能属于同一个最小生成树中。

思路：
考虑kruskal的整个过程，

当前面k条边已经完成操作的时候（就是前k小的边已经进行并查集缩点，此时部分点已经形成了若干个连通块）

这个时候突然冒出来一些权值相同并且这个权值大于前k条边最大权值的边，问这些边是否能同时被某一棵最小生成树包含。

那我们依次检查这突然冒出来的几条边，在原来的这个并查集的基础上，继续进行缩点操作。

如果这些边在处理的时候没有遇到某条边的两个点在连边之前已经连通的情况，那么这些边能同时被某一棵最小生成树包含。

反之亦然。

对于这道题我们要做的就是把所有询问离线，把每条询问边塞到对应的权值里面。

当我现在要检查权值为x的某些同一个询问里的边的时候，首先要保证那些权值小于x的边都已经进行了并查集缩点。

然后把这些权值为x的某些同一个询问里的边想象成刚刚说的“突然冒出来的几条边”，检查就可以了。

如果不行的话这个询问的id的答案就是NO了。

因为同一个权值里面可能会有（其实是一般都有）询问id不同的边，那么处理完某一批边之后我们要对询问的时候改动的并查集撤销。

开个栈记录一下即可。

问：这里问在添加第k个询问，权值为x的时候。在图中已经形成的最小生成树子图，比x小的边可能不是第k个询问。怎么能说对所有第k个都满足呢？

答：在kruskal的算法过程中。权值相同的若干条边。排序的方法不同，但是形成的每个连通块包含的点集是一样的。所有这个问题就可以不考虑了。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
typedef pair<int, int> PII;

struct node{
    int x, y, z;
}e[500010];

struct query{
    int x, y, id;
    friend bool operator < (const query &a, const query &b){
        return a.id<b.id;
    }
};

int father[500010], ret[500010], n, m, qu;
stack<PII > s;
vector<query> v[500010];
vector<PII > g[500010];

int fd(int x){
    if(father[x]<0){
        return x;
    }
    else{
        return fd(father[x]);
    }
}

void work(int x, int y){
    int fx=fd(x), fy=fd(y);
    if(fx==fy){
        return ;
    }
    if(father[fx]<=father[fy]){
        father[fx]+=father[fy];
        father[fy]=fx;

    }
    else{
        father[fy]+=father[fx];
        father[fx]=y;
    }
}

void solve(int cnt, int x, int y){

    while(!s.empty()){
        s.pop();
    }
    for (int i=x; i<=y; ++i){
        int fx=fd(v[cnt][i].x), fy=fd(v[cnt][i].y);

        if(fx==fy){//如果有一条边添加不进去就不可以
            ret[v[cnt][i].id]=1;
        }
        else if(father[fx]<=father[fy]){

            s.push(make_pair(fy, father[fy]));
            father[fy]=fx;
        }
        else{

            s.push(make_pair(fx, father[fx]));
            father[fx]=fy;
        }
    }
    while(!s.empty()){
        father[s.top().first] = s.top().second;
        s.pop();
    }
}

int main(){

    memset(father, -1, sizeof(father));

    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++){
        scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].z);
        g[e[i].z].push_back(make_pair(e[i].x, e[i].y));//按权值 保存原始边
    }
    scanf("%d", &qu);
    for(int i=1; i<=qu; i++){
        int opnum;
        scanf("%d", &opnum);
        for(int j=1; j<=opnum; j++){
            int x; scanf("%d", &x);
            v[e[x].z].push_back({e[x].x, e[x].y, i});//按权值 保存所有的查询的边
        }
    }

    for(int i=1; i<=500000; i++){
        sort(v[i].begin(), v[i].end());
    }

    for(int i=1; i<=500000; i++){
        for(int j=0; j<g[i-1].size(); j++){//把权值<i的全部添加进去。形成的每个连通块包含的点集是一样的
            work(g[i-1][j].first, g[i-1][j].second);
        }

        int sz=v[i].size();
        if(sz==0){
            continue;
        }
        int now=0;
        while(now<sz){
            int j=now;
            while(j+1<sz&&v[i][j+1].id==v[i][j].id){//找到把属于同一个询问的所有的边区间
                j++;
            }
            solve(i, now, j);//判断这个区间
            now=j+1;
        }
    }

    for(int i=1; i<=qu; i++){
        printf("%s\n", ret[i]?"NO":"YES");
    }

    return 0;
}