CF891C Envy

对于同一张图上的mst,对于任意权值的边,所有mst中这个权值的边的数量一定一样,从小到大加边后的状态也是一样的,因此,判断某些变能否在同一个mst中出现,不同权值的边之间是互不影响的

所以我们可以在每条边维护一个tx,ty,表示在更新到i之前的当前节点的父亲们,也就是在把当前边加进去后更新前的

然后对于每一个输入,只要判断一下会不会出现自环就行了

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#define maxn 550000
#define rep(x,y,z) for(register int x = y ; x <= z ; x ++)
#define per(x,y,z) for(register int x = y ; x >= z ; x --)
using namespace std ;
int read() {
	int x = 0 ,  f = 1 ; char s = getchar() ;
	while(s > '9' || s < '0') {if(s == '-') f = -1 ; s = getchar() ;}
	while(s <='9' && s >='0') {x = x * 10 + (s-'0'); s = getchar() ;}
	return x*f ;
}
int fa[maxn] ;
int find(int x) {
	if(fa[x] != x) fa[x] = find(fa[x]) ;
	return fa[x] ;
}
void merge(int x ,int y) {
	x = find(x) , y = find(y) ;
	fa[y] = x ;
}
struct dy{
	int x , y ,z , id , tx, ty ;
	int operator < (const dy x)const {
		return z < x.z ;
	}
}a[maxn] ;

bool cmp(dy x , dy y) {
	return x.id < y.id ;
}
int n ,m  ;
int main () {
	n = read() , m = read() ;
	rep(i,1,n) fa[i] = i ;
	rep(i,1,m) {
		a[i].x = read() ;
		a[i].y = read() ;
		a[i].z = read() ;
		a[i].id = i ;
	}
	sort(a+1,a+1+m) ;
	a[0].z = -1 ;
	for(int i = 1 ; i <= m ;) {
		int j = i ;
		do {
			a[j].tx = find(a[j].x) ;
			a[j].ty = find(a[j].y) ;
			j ++ ;
		}while(j <= m && a[j].z == a[j-1].z) ;
		while(i < j) {
			while(find(a[i].x) == find(a[i].y) && i < j) i ++ ;
			if(i < j) merge(a[i].x , a[i].y ) ;
		}
	}
	int q = read() ;
	sort(a+1,a+1+m,cmp) ;
	rep(i,1,n) fa[i] = i ;
	while(q --) {
		int k = read() ;
		vector<dy>v ;
		rep(i,1,k) {
			int x = read() ;
			v.push_back({a[x].tx,a[x].ty,a[x].z}) ;
		}
		sort(v.begin(),v.end()) ;
		int flag = 1 ;
		for(int i = 0 , sz = v.size()-1 ; i <= sz && flag;) {
			if(v[i].x == v[i].y) {
				flag = 0 ;
				break ;
			}
			merge(v[i].x,v[i].y) ;
			int j = i + 1 ;
			while(j <= sz && v[j].z == v[i].z) {
				if(find(v[j].x) == find(v[j].y)) {
					flag = 0 ;
					break ;
				}merge(v[j].x,v[j].y) ;j ++ ;
			}while(i < j) {
				fa[v[i].x] = v[i].x ;
				fa[v[i].y] = v[i].y ;
				i ++ ;
			}
		}
		puts(flag ? "YES" : "NO") ;
	}
	return 0 ;
}