Codeforces Round #379 (Div. 2) E: Anton and Tree

http://codeforces.com/contest/734/problem/E

問題概要

N頂点の木が与えられる。頂点は黒か白で塗られている。頂点 v を選び、頂点 v と同じ色の頂点のみを使って頂点 v から移動できるすべての頂点の色を反転する操作がおこなえる。 すべての頂点の色を統一するのに必要な最小の操作回数を求めよ。

• 1≦N≦200000

解法

あらかじめ同じ色の隣接頂点同士を縮約しておく。縮約後は、白黒が交互に現れる木になる。結論からいうと、縮約後の木の半径が答えになる。このことを証明する。

証明

適当なパスをひとつとる。

このパスをすべて同じ色に揃える回数は、この木をすべての同じ色に揃える回数以下になる。長さ N のパスをすべて同じ色に揃えるには何回の操作が必要だろうか。

○●○●○●○　というパスを考えてみる。左から 3 番目の○を反転させると ○●●●○●○ となる。これは○●○●○と置き直せる。つまり反転操作というのは○●○→○あるいは●○●→●（ただし端は若干違う）という操作と読み替えることができる。一回の操作で丸を 2 個づつ減らせるので、必要な操作回数は floor(n/2) である。

パスとして直径 D を選べば、この木をすべての同じ色に揃える回数は floor((D+1)/2) 以上であることが言える（直径の長さが D なら頂点数は D+1）。実際に中心に対して操作をし続ければ floor((D+1)/2) 回ですべての色を揃えられるため、最小であることが示された。

少なくとも答えが半径より小さくならないことに気付けば簡単。