kmjp's blog

競技プログラミング参加記です

yukicoder : No.1582 Vertexes vs Edges

辺と点で操作を分ける対戦ゲーは珍しい?
https://yukicoder.me/problems/no/1582

問題

木を成す無向グラフが与えられる。
各頂点は初期状態で白く塗られている。

ここで2人交互に操作を行う対戦ゲームを行う。
先手は、両端が白頂点の辺を選び、両端の頂点を黒く塗る。
後手は、黒頂点を1つ選び、白く塗る。

先手が操作できなくなったら終了である。
先手は黒頂点、後手は白頂点を増やそうとするとき、最終的に黒頂点は何通りか。

解法

最終的に、白頂点が隣接しない塗り方のうち白頂点が最多のものとなる。
もし後手が希望しない塗り方があれば、その両端をいったん白くリセットし、先手に黒く塗らせたのち塗り替えればよいためである。

あとは、典型。
SubTree毎に根が白・黒頂点であるとき、SubTree内の白頂点の最大数を数えていこう。

int N;
vector<int> E[202020];


int W[202020],B[202020];

void dfs(int cur,int pre) {
	W[cur]=1;
	FORR(e,E[cur]) if(e!=pre) {
		dfs(e,cur);
		W[cur]+=B[e];
		B[cur]+=max(B[e],W[e]);
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	dfs(0,0);
	
	cout<<N-max(W[0],B[0])<<endl;
	
}

まとめ

考察は手間だけど、実装は軽め。