AtCoder ARC #097 : F - Monochrome Cat

だいぶ記憶が薄れてきているなぁ。
https://beta.atcoder.jp/contests/arc097/tasks/arc097_d

問題

N頂点の木を成すグラフがある。
各頂点は白黒で塗られている。

この木を猫が任意の頂点から初めて隣接頂点を辿って移動していく。
時間1毎に猫は以下のいずれかの手順を取れる。

• 隣接点に移動し、かつ移動先の頂点を白黒反転する。
• 移動せず今のいる頂点を白黒反転する

全頂点を黒く塗るには、最小何回移動すればよいか。

解法

白頂点数が１以下の場合は自明。以下そうでない場合を考える。

葉の黒頂点は辿る必要がないので、そういうものはすべて取り除く。
そうすると葉がすべて白い状態になる。
葉が白いので全頂点を訪問するため全辺1回は通る必要があり、かつ3回通っても意味がない（1回だけ通るのと状態が変わらないので）ので、各辺は1回か2回通ることになる。
これは、言い換えるとDFS順で辺を辿る閉路から、1つ任意のパスを取り除くことに相当する。

よって、まず全辺2回通った場合の各頂点の色を求めよう。
この状態でまだ白い点がある場合、猫はその頂点で反転動作に時間を1消費する。
ただし、先ほどの１つパスを除くことを考えると、それらの点は移動を行わないことで1回反転回数が減る。

そのため、白い点をできるだけ多く通るパスを除くとよい。
これは直径と同じ要領でDPで求めることができる。

int N;
set<int> E[101010];
string C;
int dp[101010];
int ma;

int dfs(int cur,int pre) {
	vector<int> V(2,0);
	FORR(e,E[cur]) if(e!=pre) V.push_back(dfs(e,cur));
	sort(ALL(V));
	reverse(ALL(V));
	
	ma=max(ma,C[cur]+V[0]+V[1]);
	return C[cur]+V[0];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].insert(y-1);
		E[y-1].insert(x-1);
	}
	int ret=0;
	cin>>C;
	FOR(i,N) {
		C[i]=C[i]=='W';
		ret+=C[i];
	}
	if(ret==0) return _P("0\n");
	if(ret==1) return _P("1\n");
	
	queue<int> Q;
	FOR(i,N) if(E[i].size()==1) Q.push(i);
	
	while(Q.size()) {
		x=Q.front();
		Q.pop();
		if(C[x]==0) {
			C[x]=2;
			y=*E[x].begin();
			E[y].erase(x);
			if(E[y].size()==1) Q.push(y);
		}
	}
	ret=-2;
	int root;
	FOR(i,N) if(C[i]!=2) {
		C[i]^=(E[i].size()%2);
		//cout<<i<<" "<<(int)C[i]<<endl;
		ret+=2+C[i];
		root=i;
	}
	dfs(root,-1);
	//cout<<ret<<" "<<ma<<endl;
	cout<<ret-2*ma<<endl;
	
}

まとめ

本番だとすんなり思いつかなさそう。