ARC 097 F Monochrome Cat

AtCoder

問題

N頂点からなり、各頂点が黒または白である木が与えられる。
好きな頂点から出発して、

  • 今いる頂点の色を反転させる
  • 隣接する頂点に移動して、移動先の色を反転させる

の二つの操作を好きなだけ行える。全部の頂点の色を黒にするのにかかる操作の回数の最小値を求めよ。終了時にはどこにいてもいい。
https://beta.atcoder.jp/contests/arc097/tasks/arc097_d

制約条件

N≦10^5

方針

通るべき頂点は、白の頂点と白の頂点のパス上にある頂点だけ。
よって、木の黒い葉の頂点を消すという操作を好きなだけ繰り返してよい。以下、その操作をし終えた状態として考える。


木の各辺は３回以上通る必要はない（一回目にその辺を渡ったときに全部の用事を済ませればいい）から、移動の軌跡はオイラーツアーから一つのパスを取り除いたようなパスになる。
取り除くパスとその向きを決めると、かかるコストは一意に定まる。


取り除くパスは、全ての頂点vについて、vから葉の向きに伸びるパスのうちコストの最適なもの
葉のほうからvに到着するパスのうちコストの最適なものをそれぞれ求めれば全部の可能性を列挙できる。

(stub)

ソースコード

int dp[100010][2]; //dp[v][下向き]
int n, col[100010], deg[100010], white[100010], cost, ans;
vector<vi> e;

void rec(int c, int p){
	white[c] += col[c];
	vector<pi> a, b;
	
	deg[c] = c != p;
	for(int i : e[c]) if(i != p){
		rec(i, c);
		if(!white[i]) continue;
		deg[c]++;
		white[c] += white[i];
		cost += 2;
	}
	if(!white[c]) return;
	
	for(int i : e[c]) if(i != p && white[i]){
		dp[c][0] = max(dp[c][0], dp[i][0] + (col[c] != deg[c] % 2) - (col[c] != (deg[c] + 1) % 2) + 1);
		dp[c][1] = max(dp[c][1], dp[i][1] + (col[i] != deg[i] % 2) - (col[i] != (deg[i] + 1) % 2) + 1);
		
		a.emplace_back(dp[i][0] + (col[c] != deg[c] % 2) - (col[c] != (deg[c] + 1) % 2) + 1, i);
		b.emplace_back(dp[i][1] + (col[i] != deg[i] % 2) - (col[i] != (deg[i] + 1) % 2) + 1, i);
	}
	if(col[c] != deg[c] % 2) cost++;
	sort(all(a), greater<pi>()); sort(all(b), greater<pi>());
	if(a.size()) ans = max(ans, a[0].first);
	if(b.size()) ans = max(ans, b[0].first);
	
	rep(i, 2) rep(j, 2) if(i < a.size() && j < b.size() && a[i].second != b[j].second){
		ans = max(ans, a[i].first + b[j].first);
	}
}

int main(){
	cin.tie(0); cin.sync_with_stdio(0);
	cin >> n; e.resize(n);
	rep(i, n - 1){
		int a, b; cin >> a >> b; a--; b--;
		e[a].pb(b);
		e[b].pb(a);
	}
	{
		string s; cin >> s;
		rep(i, n) col[i] = s[i] == 'W';
	}
	rep(i, n) if(col[i]){
		rec(i, i);
		break;
	}
	cout << cost - ans << endl;
	
	return 0;
}