Codeforces #403 (Div. 2) C: Andryusha and Colored Balloons

解法

木の問題は、根付き木にすると見通しが立てやすくなることが多い。

根から再帰的に色を塗っていく。

ある頂点vの色をcur_col, 親の色をpar_colとする。また、部分木vのうち色が決まっているのはvだけとする。子の色を決めたい。問題文中の色を塗る条件をわかりやすく言い換えると、距離2以内の頂点の色は異なるということになる。あるvの子c[i]の色に対して、距離2以内に来る頂点ですでに色が決まっている、または一緒に色を決めなければならない頂点は以下の通り。

(1) 頂点v(cur_col)

(2) 頂点vの親(par_col)

(3) 別のvの子c[j] (i!=j)

つまり、下の図のように塗れば良い。

根の処理だけ特殊になるが、根を実際には存在しない頂点0の子とし、頂点0の色を実際には存在しない色0で塗っておけば、頂点0の子として色を塗れる。

思いつき方

根付き木にして描いてみる。

f:id:parukii:20170306111411j:plain

広告を非表示にする