Codeforces #681 Div1 E. Black, White and Grey Tree

初手が思いつくかがカギ。
https://codeforces.com/contest/1442/problem/E

問題

木を成すグラフが与えられる。
各点は、白・黒・灰色のいずれかが振られている。
このグラフに対し、以下の手順で頂点を消していく。

• 単一の連結成分内にある頂点の集合と、そこにつながる辺を消す。ただし、白点と黒点を同時に消してはならない。

全点を消すのにかかる最小処理回数は何回か。

解法

白黒点が交互に並んだ一直線のグラフを考える。
この場合、両端の白点・黒点を交互に消すのが良い。
むやみに連結成分が分解されてしまうと、必要な手数が増えるのでよろしくない。

一直線でない場合どうするか。
これは葉から交互に消していくのが良い。
初手で白点と黒点で始めるケースそれぞれについて、ダイクストラ法の要領で最寄の葉から何手目で消せるか見ていこう。

int T;
int N;
int A[202020];
vector<int> E[202020];
set<int> S[202020];

int hoge(int turn) {
	int i;
	if(N==1) return 1;
	queue<int> Q,nex;
	FOR(i,N) {
		S[i].clear();
		FORR(e,E[i]) S[i].insert(e);
		if(E[i].size()==1) {
			if(A[i]==0||A[i]==turn+1) Q.push(i);
			else nex.push(i);
		}
	}
	
	int num=0;
	while(Q.size()||nex.size()) {
		num++;
		while(Q.size()) {
			int x=Q.front();
			Q.pop();
			FORR(e,E[x]) {
				S[e].erase(x);
				if(S[e].size()==1) {
					if(A[e]==0||A[e]==turn+1) Q.push(e);
					else nex.push(e);
				}
			}
		}
		
		swap(nex,Q);
		turn^=1;
	}
	return num;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) {
			cin>>A[i];
			E[i].clear();
		}
		FOR(i,N-1) {
			cin>>x>>y;
			E[x-1].push_back(y-1);
			E[y-1].push_back(x-1);
		}
		cout<<min(hoge(0),hoge(1))<<endl;
	}
}

まとめ

Eとはいえ1750ptなので普段の問題よりは易しめ。