2831 Can we build this one?

http://poj.org/problem?id=2831
N村を結ぶM辺があり、最小全域木を作る
そのとき、ある辺のコストがCならその辺は最小全域木に選ばれうるか、という
クエリを処理する問題

id:semiexpさんの　http://d.hatena.ne.jp/semiexp/20110107/1294381308　こちらの方が想定解だと思いますが、
この解法ではクラスカル法で辺を50処理するごとにその状態を記録して、一番近いところから
探索を再び始める、という方法をとっています
O(MlogM+A(M)+Q(log(M/50)+A(50)))

struct uf{
	vi rank,p;
	uf(int n){
		rank.resize(n,1);
		p.resize(n,-1);
	}
	int root(int a){
		if(p[a]==-1) return a;
		return p[a]=root(p[a]);
	}
	bool same(int a,int b){
		return root(a)==root(b);
	}
	void unite(int a,int b){
		a=root(a);b=root(b);
		if(a==b) return;
		if(rank[a]>rank[b]) p[b]=a;
		else{
			p[a]=b;
			if(rank[a]==rank[b]) ++rank[b];
		}
	}
};
int sq=50;
int main(){
	int n,m,q;scanf("%d%d%d",&n,&m,&q);
	vector<pair<int,pi> >es(m),es2;
	REP(i,m){
		int a,b,c;scanf("%d%d%d",&a,&b,&c);
		--a;--b;
		es[i]=mp(c,mp(a,b));
	}
	es2=es;
	sort(ALL(es2));
	uf u(n);
	vector<uf> point(2002,uf(n));
	REP(i,es2.size()){
		if(i%sq==0){
			point[i/sq]=u;
		}
		u.unite(es2[i].sc.fr,es2[i].sc.sc);
	}
	uf bef(0);
	REP(i,q){
		int road,x;scanf("%d%d",&road,&x);
		--road;
		pair<int,pi> r=es[road];
		r.fr=x;
		int ub=(m+sq-1)/sq,lb=0;
		while(ub-lb>1){
			int md=(ub+lb)/2;
			if(es2[md*sq].fr>=r.fr) ub=md;
			else lb=md;
		}
		int suc=0;
		bef=point[lb];
		if(!bef.same(r.sc.sc,r.sc.fr)){
		REP(j,sq){
			if(lb*sq+j==m){suc=1;break;}
			if(es2[lb*sq+j].fr<r.fr){
				bef.unite(es2[lb*sq+j].sc.fr,es2[lb*sq+j].sc.sc);
				if(bef.same(r.sc.sc,r.sc.fr)) break;
			}else{
				suc=1;break;
			}
			if(j==sq-1){suc=1;break;}
		}
		}
		if(suc) printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}

超絶無駄実装！！