/****************************************\
* Author : ztx
* Title  : [WC2006]水管局长数据加强版
* ALG    : LCT+Kruskal+离线
* CMT    : 通过构建最小生成树,然后转换成 寻找最近公共祖先来求解, 逆序处理询问,将删除改成添加边
* Time   :
\****************************************/

/****************************************\
* Author : ztx
* Title  : [WC2006]水管局长数据加强版
* ALG    : LCT+Kruskal+离线
* CMT    : 通过构建最小生成树,然后转换成 寻找最近公共祖先来求解, 逆序处理询问,将删除改成添加边
* Time   :
\****************************************/

#include <cstdio>
#include <algorithm>
	
int CH , NEG ;

inline int GETCHAR() {
	static const int LEN = 1<<15 ;
	static char BUF[LEN] , *S = BUF , *T = BUF ;
	if (S == T) {
		T = (S=BUF)+fread(BUF , 1 , LEN , stdin) ;
		if (S == T) return EOF ;
	}
	return *S ++ ;
}

inline void read(int& ret) {
    ret = 0 ; while (CH=GETCHAR() , CH<'!') ;
    while (ret = (ret<<1)+(ret<<3)+CH-'0' , CH=GETCHAR() , CH>'!') ;
}

#define  maxn  100010LL
#define  maxm  1000010LL
#define  maxt  1100010LL
#define  maxe  2000010LL

int n , m , Q ;


struct EDGE { int u , v , w , id , del ; } e[maxm] ;
struct QUE { int cmd , u , v , id , ans ; } q[maxm] ;

bool CmpT(const EDGE& a , const EDGE& b) {
	if (a.u == b.u) return a.v < b.v ;
	else return a.u < b.u ;
}
bool CmpW(const EDGE& a , const EDGE& b) { return a.w < b.w ; }
bool CmpID(const EDGE& a , const EDGE& b) { return a.id < b.id ; }

int L , M , R ;
inline int Bsearch(int u , int v) {
	L = 1 , R = m ;
	while (R-L > 1) {
		/* (L , R] */
		M = L+(R-L)/2 ;
		if (e[M].u<u || (e[M].u==u&&e[M].v<v)) L = M ;
		else R = M ;
	}
	return R ;
}


int fa[maxt] = {0} , ch[maxt][2] = {0} ;
int maxv[maxt] = {0}/*Here are the labels stored*/ , val[maxt] = {0} ;
bool rev[maxt] = {0} ;

#define  null     0LL
#define  left(u)  ch[u][0]
#define  right(u) ch[u][1]

inline void Exchange(int& a , int& b) { int c = a ; a = b ; b = c ; }

inline bool isrt(int u) { return (fa[u]==null)||(left(fa[u])!=u&&right(fa[u])!=u) ; }

inline void Maintain(int u) {
	maxv[u] = u ;
	if (left(u) && val[maxv[left(u)]]>val[maxv[u]]) maxv[u] = maxv[left(u)] ;
	if (right(u) && val[maxv[right(u)]]>val[maxv[u]]) maxv[u] = maxv[right(u)] ;
}

inline void Clear(int u) {
	if (!u) return ;
	if (!isrt(u)) Clear(fa[u]) ;
	if (rev[u]) {
		rev[u] = false ;
		rev[left(u)] ^= true ;
		rev[right(u)] ^= true ;
		Exchange(left(u) , right(u)) ;
	}
}

inline void zig(int x) {
    /* right rotate */
    int y = fa[x] , z = fa[y] ;
    if (left(z) == y) left(z) = x ; else if(right(z) == y) right(z) = x ; fa[x] = z ;
    fa[right(x)] = y ; left(y) = right(x) ; fa[y] = x ; right(x) = y ;
    Maintain(y) , Maintain(x) ;
}
 
inline void zag(int x) {
    /* left rotate */
    int y = fa[x] , z = fa[y] ;
    if (left(z) == y) left(z) = x ; else if(right(z) == y) right(z) = x ; fa[x] = z ;
    fa[left(x)] = y ; right(y) = left(x) ; fa[y] = x ; left(x) = y ;
    Maintain(y) , Maintain(x) ;
}

inline void Splay(int x) {
	Clear(x) ;
	int y , z ;
	while (!isrt(x)) {
		y = fa[x] , z = fa[y] ;
		if (isrt(y)) {
			if (left(y) == x) zig(x) ; else zag(x) ;
		} else {
			if (left(z) == y) {
				if (left(y) == x) zig(x) , zig(x) ;
				else zag(x) , zig(x) ;
			} else if (right(z) == y) {
				if (right(y) == x) zag(x) , zag(x) ;
				else zig(x) , zag(x) ;
			}
		}
	}
}

inline void Access(int u) {
	for (int v = null ; u ; u = fa[u]) Splay(u) , right(u) = v , v = u , Maintain(u) ;
}

inline void Makeroot(int u) {
	Access(u) , Splay(u) , rev[u] ^= true ;
}

inline void Link(int u , int v) {
	Makeroot(u) , fa[u] = v ;
}

inline void Cut(int u , int v) {
	Makeroot(u) ; Access(v) , Splay(v) , fa[u] = left(v) = null ;
}

inline int Query(int u , int v) {
	Makeroot(u) ; Access(v) , Splay(v) ; return maxv[v] ;
}


int f[maxn] = {0} ;
inline int Father(int u) { return f[u] ? f[u] = Father(f[u]) : u ; }
inline bool Union(int u , int v) {
	u = Father(u) , v = Father(v) ;
	if (u == v) return false ;
	f[u] = v ; return true ;
}

int i , j , u , v , k , cnt = 0 ;
int main() {
	#define READ
	#ifdef  READ
		freopen("tube_strong.in" ,"r",stdin ) ;
		freopen("tube_strong.out","w",stdout) ;
	#endif

	read(n) , read(m) , read(Q) ;
	for (i = 1 ; i <= m ; i ++ ) {
		read(e[i].u) , read(e[i].v) , read(e[i].w) ;
		if (e[i].u > e[i].v) Exchange(e[i].u , e[i].v) ;
	}
	
	std::sort(e+1 , e+m+1 , CmpW) ;
	for (i = 1 ; i <= m ; i ++ ) {
		e[i].id = i ;
		val[i+n] = e[i].w , maxv[i+n] = i+n ;
		/* Edges are regarded as points */
	}
	/* Mark */
	std::sort(e+1 , e+m+1 , CmpT) ;
	for (i = 1 ; i <= Q ; i ++ ) {
		read(q[i].cmd) , read(q[i].u) , read(q[i].v) ;
		if (q[i].cmd == 2) {
			if (q[i].u > q[i].v) Exchange(q[i].u , q[i].v) ;
			j = Bsearch(q[i].u , q[i].v) ;
			e[j].del = true , q[i].id = e[j].id ;
		}
	}
	
	/* Kruskal */
	std::sort(e+1 , e+m+1 , CmpID) ;
	for (i = 1 ; i <= m ; i ++ ) {
		if (!e[i].del && Union(e[i].u , e[i].v)) {
			cnt ++ ;
			Link(e[i].u , i+n) ; Link(e[i].v , i+n) ;
			if (cnt == n-1) break ;
		}
	}
	
	for (i = Q ; i ; i -- ) {
		if (q[i].cmd == 1) q[i].ans = val[Query(q[i].u , q[i].v)] ;
		else {
			u = q[i].u , v = q[i].v , k = q[i].id ;
			j = Query(u , v) ;
			if (e[k].w < e[j-n].w) {
				Cut(e[j-n].u , j) , Cut(e[j-n].v , j) ;
				Link(u , k+n) , Link(v , k+n) ;
			}
		}
	}
	
	for (i = 1 ; i <= Q ; i ++ )
		if (q[i].cmd == 1) printf("%d\n", q[i].ans ) ;

	#ifdef  READ
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
	return 0 ;
}
/*
4 4 3
1 2 2
2 3 3
3 4 2
1 4 2
1 1 4
2 1 4
1 1 4
*/

• 相关文章
• 全局相关文章