线段树分治维护并查集

第八组挂了，调不出来了，求路过大佬帮助。

#include <iostream>
#include <cstring>
#include <vector>
using namespace std ;

const int N = 500005 ;
int n , m , q , kl , top , ans[N] , dep[N*105] , fa[N*105] , col[N] , ti[N] ;

struct Node {
	int u , v , k , c ;
	Node ( int _u = 0 , int _v = 0 , int _k = 0 , int _c = 0 ) :
		u ( _u ) , v ( _v ) , k ( _k ) , c ( _c ) { }
} p[N] , st[N] , vt[N] ;

vector < Node > vc[N<<2] ;

void change ( int k , int l , int r , int x , int y , int z , int kc ) {
	if ( x <= l && r <= y ) {
		vc [ k ] .push_back ( Node ( z , kc ) ) ;
		return ;
	}
	int mid = ( l + r ) >> 1 ;
	if ( x <= mid )
		change ( k << 1 , l , mid , x , y , z , kc ) ;
	if ( y > mid )
		change ( k << 1 | 1 , mid + 1 , r , x , y , z , kc ) ;
}

int id ( int x , int k , int op ) {
	return x + ( k - 1 ) * 2 * n + op * n ;
}

int find ( int x ) {
	if ( fa [ x ] == x )
		return x ;
	return find ( fa [ x ] ) ;
}

void merge ( int x , int y ) {
	x = find ( x ) , y = find ( y ) ;
	if ( x == y ) return ;
	if ( dep [ x ] < dep [ y ] )
		swap ( x , y ) ;
	fa [ y ] = x ;
	if ( dep [ x ] == dep [ y ] )
		++ dep [ x ] ;
	st [ ++ top ] = Node ( x , y ) ;
}

void solve ( int k , int l , int r ) {
	int tp = top ;
	int siz = vc [ k ] .size ( ) ;
	for ( int i = 0 ; i < siz ; ++ i ) {
		int tmp = vc [ k ] [ i ] .u , kc = vc [ k ] [ i ] .v ;
		int u = p [ tmp ] .u , v = p [ tmp ] .v ;
		merge ( id ( u , kc , 0 ) , id ( v , kc , 1 ) ) ;
		merge ( id ( u , kc , 1 ) , id ( v , kc , 0 ) ) ;
	}
	if ( l == r ) {
		Node tmp = vt [ l ] ;
		int kc = tmp .c , u = p [ tmp .k ] .u , v = p [ tmp .k ] .v ;
		if ( find ( id ( u , kc , 0 ) ) == find ( id ( v , kc , 0 ) ) || find ( id ( u , kc , 1 ) ) == find ( id ( v , kc , 1 ) ) ) {
			if ( col [ tmp .k ] ) {
				change ( 1 , 1 , q , l + 1 , tmp .v , tmp .k , col [ tmp .k ] ) ;
			}
			return ;
		}
		if ( l + 1 <= tmp .v )
			change ( 1 , 1 , q , l + 1 , tmp .v , tmp .k , kc ) ;
		col [ tmp .k ] = kc ;
		ans [ l ] = 1 ;
		return ;
	}
	int mid = ( l + r ) >> 1 ;
	solve ( k << 1 , l , mid ) ;
	solve ( k << 1 | 1 , mid + 1 , r ) ;
	while ( top > tp ) {
		int x = st [ top ] .u , y = st [ top ] .v ;
		fa [ y ] = y ;
		if ( dep [ x ] == dep [ y ] + 1 )
			-- dep [ x ] ;
		-- top ;
	}
}

void dfs ( int k , int l , int r ) {
	if ( l == r ) {
		cout << " vt : " << l << " - " << r << "\n" ;
		Node tmp = vt [ l ] ;
		cout << tmp .u << " - " << tmp .v << " : " << tmp .k << " , " << tmp .c << "\n" ;
		cout << "\n" ;
		return ;
	}
	int mid = ( l + r ) >> 1 ;
	dfs ( k << 1 , l , mid ) ;
	dfs ( k << 1 | 1 , mid + 1 , r ) ;
}

int main ( ) {
//	freopen ( "data.in" , "r" , stdin ) ;
//	freopen ( "data.ans" , "w" , stdout ) ;
	cin >> n >> m >> kl >> q ;
	for ( int i = 1 ; i <= n * 2 * kl ; ++ i )
		fa [ i ] = i ;
	for ( int i = 1 ; i <= m ; ++ i )
		cin >> p [ i ] .u >> p [ i ] .v ;
	for ( int i = 1 ; i <= q ; ++ i ) {
		int x , y ;
		cin >> x >> y ;
		if ( col [ x ] ) {
			vt [ ti [ x ] ] = Node ( ti [ x ] , i - 1 , x , col [ x ] ) ;
		}
		ti [ x ] = i ;
		col [ x ] = y ;
	}
	for ( int i = 1 ; i <= m ; ++ i ) {
		if ( col [ i ] ) {
			vt [ ti [ i ] ] = Node ( ti [ i ] , q , i , col [ i ] ) ;
		}
	}
	memset ( col , 0 , sizeof ( col ) ) ;
	solve ( 1 , 1 , q ) ;
	for ( int i = 1 ; i <= q ; ++ i )
		puts ( ans [ i ] ? "YES" : "NO" ) ;
	return 0 ;
}