AtCoder AGC #014 : E - Blue and Red Tree

本番HL分解で頑張ろうとしてダメでした。
http://agc014.contest.atcoder.jp/tasks/agc014_e

問題

N頂点と(N-1)本の青い辺と(N-1)本の赤い辺からなるグラフがある。
青い辺と赤い辺はそれぞれ木を成す配置である。

初期状態で、このグラフのうち青辺だけからなるものを考える。
このグラフに赤辺(u-v)を追加するとき、青辺で(u-v)が連結してなければならず、また(u-v)間の青辺を1つ取り除くものとする。
追加する赤辺や取り除く青辺の順番を任意に入れ替えられるとき、青辺だけのグラフから赤辺だけのグラフに作り替えられるか。

解法

赤辺を追加する際青辺を1個取り除くということは、この一連の追加・削除を行った後、青辺と赤辺を合わせて構成されるグラフは閉路を持たず木である。
また、以降の処理では青辺で連結している頂点間で構成される赤辺のみ追加可能である。

つまり、取り除く青辺だけで構成されるグラフを順次考えていくと、赤辺で構成されるグラフと連結状態が同じことになる。
よってその状態を再現しよう。

初期状態でN点がすべて孤立しており、青辺と赤辺を1個ずつ追加していく。
その際、両辺の端点が属する連結成分が同じような２つの連結成分があれば、それらを連結する、という処理を繰り返す。
最終的に全頂点が単一の連結成分を構築できれば条件を満たすし、そうでなければ満たさない。

連結処理では連結成分内の頂点を端点とする辺を縮約していく必要があるため、そこはいわゆるマージテクを用いて辺のデータのコピー量が少なくなるようにしよう。

int N;
set<int> E[101010][2];
set<pair<int,int>> S;

void add_edge(int a,int b) {
	if(E[a][0].count(b)) {
		E[a][0].erase(b);
		E[b][0].erase(a);
		S.insert({min(a,b),max(a,b)});
		E[a][1].insert(b);
		E[b][1].insert(a);
	}
	else {
		E[a][0].insert(b);
		E[b][0].insert(a);
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	int id=-1;
	FOR(i,2*(N-1)) {
		cin>>x>>y;
		add_edge(x-1,y-1);
	}
	
	FOR(i,N-1) {
		if(S.empty()) return _P("NO\n");
		x = S.begin()->first;
		y = S.begin()->second;
		S.erase(S.begin());
		E[x][1].erase(y);
		E[y][1].erase(x);
		
		if(E[x][0].size()+E[x][1].size()<E[y][0].size()+E[y][1].size()) {
			swap(x,y);
		}
		// merge y->x
		FORR(e,E[y][0]) if(x!=e) {
			E[e][0].erase(y);
			add_edge(x,e);
		}
		E[y][0].clear();
		
		FORR(e,E[y][1]) if(x!=e) {
			E[e][1].erase(y);
			E[e][1].insert(x);
			E[x][1].insert(e);
			S.erase({min(e,y),max(e,y)});
			S.insert({min(x,e),max(x,e)});
		}
		
	}
	return _P("YES\n");
}

まとめ

HL分解だと、青辺と赤辺のマッチング処理は行えても処理の順番がわからずダメっぽい？