#define N 20005  
struct Treap{  
	Treap *ch[2];  
	int r;          //数字越大，优先级越高  
	int v;          //值  
	int size;       //子树的节点数  
	Treap(int v):v(v) { ch[0]=ch[1]=NULL; r=rand(); size=1;}  
	bool operator < (const Treap& rhs) const{  
		return r < rhs.r;  
	}  
	int cmp(int x) const{  
		if(x == v)return -1;  
		return x < v ? 0 : 1;  
	}  
	void maintain(){  //以该点为根的子树节点数(包括自己)
		size = 1;  
		if(ch[0] != NULL) size += ch[0]->size;  
		if(ch[1] != NULL) size += ch[1]->size;  
	}  
};  
Treap* root[N];  

void rotate(Treap* &o, int d){  
	Treap* k = o->ch[d^1]; o->ch[d^1] = k->ch[d]; k->ch[d] = o;  
	o->maintain(); k->maintain(); o = k;  
}  

void insert(Treap* &o, int x){  
	if(o == NULL)  o = new Treap(x);  
	else {  
		int d = (x < o->v ? 0 : 1);  
		insert(o->ch[d], x);  
		if(o->ch[d] > o) rotate(o, d^1);  
	}  
	o->maintain();  
}  

void remove(Treap* &o, int x){  
	int d = o->cmp(x);  
	if(d == -1){  
		Treap* u = o;  
		if(o->ch[0] != NULL && o->ch[1] != NULL){  
			int d2 = (o->ch[0] > o->ch[1] ? 1: 0);  
			rotate(o, d2); remove(o->ch[d2], x);  
		}  
		else {  
			if(o->ch[0] == NULL) o = o->ch[1]; else o = o->ch[0];;  
			delete u;  
		}  
	}  
	else remove(o->ch[d], x);  
	if(o != NULL) o->maintain();  
}  

int kth(Treap* o, int k){  
	if(o == NULL || k<=0 || k> o->size) return 0;  
	int s = (o->ch[1] == NULL ? 0 : o->ch[1]->size);  
	if( k == s+1) return o->v;  
	else if(k <= s) return kth(o->ch[1], k);  
	else return kth(o->ch[0], k - s - 1);  
}  

void mergeto(Treap* &src, Treap* &dest){  
	if(src->ch[0] != NULL) mergeto(src->ch[0], dest);  
	if(src->ch[1] != NULL) mergeto(src->ch[1], dest);  
	insert(dest, src->v);  
	delete src;  
	src = NULL;  
}  

void removetree(Treap* &x){  
	if(x->ch[0] != NULL) removetree(x->ch[0]);  
	if(x->ch[1] != NULL) removetree(x->ch[1]);  
	delete x;  
	x = NULL;  
}  

void add_edge(int x){  
	int u = findset(from[x]), v = findset(to[x]);  
	if(u != v){  
		if(root[u]->size < root[v]->size) { fa[u] = v; mergeto(root[u], root[v]);}  
		else { fa[v] = u; mergeto(root[v], root[u]);}  
	}  
}  

treap树模版