UTPC 2014 : I - 盆栽

言われてみると簡単なんだけどな。
http://utpc2014.contest.atcoder.jp/tasks/utpc2014_i

問題

N頂点と重み付無向辺からなる木を成すグラフが与えられる。
以下のクエリが与えられるので、順次処理せよ。

• 辺番号が与えられるので、(その辺が残っていたら)重みを指定された分増す。
• 辺番号が与えられるので、(その辺が残っていたら)その辺を含む連結成分からなるグラフのうち、重みが最小のもの答え、その辺を削除する。

解法

Editorialを見て回答。

連結成分内の辺をsetで管理すれば、重みが最小のものは容易に取り出せる。
問題は辺の削除による連結成分の分割である。

ここはいわゆる「データ構造をマージする一般的なテク」を用いる。
すなわち連結成分の分割により2つの連結成分になるが、そのうち要素が少ない方を元のsetから追い出し、新しいsetにしていけば良い。
こうすると1回の辺削除でset間を移動する辺の数は徐々に減っていき、時間内に間に合うようになる。

コードは長いけど、やっていることは上記の内容なので割と単純。

set<pair<int,int> > E[101000];
int N,Q;
int A[101000],B[101000],ID[101000];
int vis[101000];
int W[101000];
set<pair<int,int> > NE[101000];

void solve() {
	int i,j,k,l,r,x,y,cq; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y>>W[i];
		A[i]=x-1;
		B[i]=y-1;
		E[A[i]].insert(make_pair(i,B[i]));
		E[B[i]].insert(make_pair(i,A[i]));
		NE[0].insert(make_pair(W[i],i));
	}
	
	cin>>Q;
	FOR(cq,Q) {
		cin>>i>>x;
		x--;
		if(i==1) {
			cin>>y;
			if(ID[x]!=-1) {
				NE[ID[x]].erase(make_pair(W[x],x));
				W[x]+=y;
				NE[ID[x]].insert(make_pair(W[x],x));
			}
		}
		else if(i==2) {
			int id=ID[x];
			if(id==-1) {
				cout<<-1<<endl;
				continue;
			}
			x=NE[id].begin()->second;
			cout<<x+1<<endl;
			
			ID[x]=-1;
			NE[id].erase(NE[id].begin());
			E[A[x]].erase(make_pair(x,B[x]));
			E[B[x]].erase(make_pair(x,A[x]));
			
			queue<pair<int,set<pair<int,int> >::iterator> > q[2];
			vector<int> v[2];
			q[0].push(make_pair(A[x],E[A[x]].begin()));
			q[1].push(make_pair(B[x],E[B[x]].begin()));
			vis[A[x]]=vis[B[x]]=cq+1;
			v[0].push_back(A[x]);
			v[1].push_back(B[x]);
			
			while(q[0].size() && q[1].size()) {
				FOR(i,2) {
					while(q[i].size()) {
						auto& qe = q[i].front();
						while(qe.second != E[qe.first].end()) {
							y = (qe.second++)->second;
							if(vis[y] != cq+1) {
								vis[y] = cq+1;
								q[i].push(make_pair(y,E[y].begin()));
								v[i].push_back(y);
								goto out;
							}
						}
						q[i].pop();
					}
					out:
					;
				}
			}
			int smaller = q[0].size()>q[1].size();
			FORR(r,v[smaller]) {
				FORR(e2,E[r]) if(e2.second<r) {
					ID[e2.first]=cq+1;
					NE[id].erase(make_pair(W[e2.first],e2.first));
					NE[cq+1].insert(make_pair(W[e2.first],e2.first));
				}
			}
		}
	}
}

まとめ

自力でたどり着けるといいんだけどな。