Codeforces Global Round 9 : G. Tree Modification

変な設定の問題。
https://codeforces.com/contest/1375/problem/G

問題

木を成すグラフが与えられる。
ここに対し、以下の処理を行う。

• a-b-cとつながった3つの頂点を選択する。
  • aにつながるb以外の頂点dについて、a-dの辺を切ってc-dと接続しなおす。
  • a-bの辺を切ってa-cと接続しなおす

グラフをスター型にするのに必要な処理は最低何回か。

解法

上記処理を行うと、aはcへの距離が1、dはcへの距離が2縮まる。
このグラフを二部グラフと考えると、上記処理は二部グラフにおいて1頂点だけ反対側のグループに動かすことに相当する。
そこで、初期状態で二部グラフのうち頂点数が少ない方について、(頂点数-1)が解。

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

void dfs(int cur,int pre,int c) {
	C[c]++;
	FORR(e,E[cur]) if(e!=pre) dfs(e,cur,c^1);
}

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,0);
	cout<<min(C[0],C[1])-1<<endl;
}

まとめ

考察ができると実装は非常に楽な回。