parukii https://blog.hatena.ne.jp/parukii/ parukiのブログ https://par.hateblo.jp/ 木 グラフ彩色 再帰 解法 木の問題は、根付き木にすると見通しが立てやすくなることが多い。 根から再帰的に色を塗っていく。 ある頂点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) つまり、下の図のよ… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fpar.hateblo.jp%2Fentry%2F2017%2F03%2F06%2F111644" title="Codeforces #403 (Div. 2) C: Andryusha and Colored Balloons - parukiのブログ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/p/parukii/20170306/20170306111411.jpg Hatena Blog https://hatena.blog 2017-03-06 11:16:44 rich https://par.hateblo.jp/entry/2017/03/06/111644 1.0 100%