题目

传送门 to luogu

思路

一开始以为是 $\tt lct$ 硬刚。结果看题解发现了更优美的解法！

注意到这样一个性质，所有的最小生成树，某个权值的边的数量相同。也就是说，无论你怎样选择，最终都会选出 $c_w$ 条权值为 $w$ 的边。

证明？不需要啊 😂 显然加入了权值不超过 $w$ 的边之后，形成的连通块是不变的，无论怎么选边。那么权值为 $w$ 的边的数量显然就是连通块大小作差。

所以把所有询问拆成小询问（毕竟连通性总是不变），然后排序。查询相当于把权值严格小于的全部加入并查集，然后加入这些边，看会不会形成环。回退就行。

代码

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long int_;
inline int readint(){int a = 0; char c = getchar(), f = 1;for(; c<'0'||c>'9'; c=getchar())if(c == '-') f = -f;for(; '0'<=c&&c<='9'; c=getchar())a = (a<<3)+(a<<1)+(c^48);return a*f;
}const int MaxN = 500005;struct UFS{int fa[MaxN], rnk[MaxN];vector< int > zxy; // fuckedvoid init(int n){for(int i=1; i<=n; ++i)fa[i] = i, rnk[i] = 1;zxy.clear();}inline int find(int a) const {for(; a^fa[a]; a=fa[a]);return a; // 直接跳到根}inline bool merge(int a,int b){int x = find(a), y = find(b);if(x == y) return false;if(rnk[x] > rnk[y]) swap(x,y);fa[x] = y, rnk[y] += rnk[x];zxy.push_back(x); return 1;}void stepBack(){int x = zxy.back();rnk[fa[x]] -= rnk[x];fa[x] = x, zxy.pop_back();}
};struct Edge{int a, b, v;bool operator < (const Edge &t) const {return v < t.v; // 按照 v 排序}
};
Edge ori[MaxN], e[MaxN];struct Query{int id, k; // 第 id 组询问，关于第 k 条边bool operator < (const Query &t) const {if(ori[k].v != ori[t.k].v)return ori[k].v < ori[t.k].v;return id < t.id; // id 相同放一块儿}
};
Query ask[MaxN];bool ans[MaxN]; UFS xyx;
int n, m, q, tot; // basic info
void solve(){int p = 1; // [1,p)的小询问已考虑for(int i=1,nxt; i<=m; i=nxt){/* 考虑边权为 e[i].v 的 */ ;while(p <= tot &&ori[ask[p].k].v == e[i].v){ans[ask[p].id] =ans[ask[p].id]&& xyx.merge(ori[ask[p].k].a,ori[ask[p].k].b);if(p <= tot && // 下一个换了个询问ask[p+1].id != ask[p].id)while(!xyx.zxy.empty())xyx.stepBack();++ p; // 无论如何，去下一个询问}/* 然后加入所有边权为 e[i].v 的 */ ;for(nxt=i; nxt<=m; ++nxt)if(e[nxt].v != e[i].v) break;else xyx.merge(e[nxt].a,e[nxt].b);xyx.zxy.clear(); // 这些边不回退}for(int i=1; i<=q; ++i)puts(ans[i] ? "YES" : "NO");
}int main(){n = readint(), m = readint();for(int i=1; i<=m; ++i){e[i].a = readint();e[i].b = readint();e[i].v = readint();ori[i] = e[i]; // 一个排序一个不}q = readint(), tot = 0;for(int i=1; i<=q; ++i){int lj = readint();while(lj --){ask[++ tot].id = i;ask[tot].k = readint();}ans[i] = true; // 先肯定}sort(ask+1,ask+tot+1);sort(e+1,e+m+1);xyx.init(n), solve();return 0;
}