drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ AtCoder AtCoder400点 ABC-D グラフ DFS BFS 色に関する問題 構築 最適化の考察：「≦ K であること」と「= K となる実例」を示す 復元 木 木DP 彩色問題 緑色diff DFS木やBFS木を考察する 【問題集】DFS・BFSのステップアップ 【問題集】木の探索 NoviSteps2Q 軽めの構築問題！！ 今回は「最大次数」というのが割と明らかだけど、しっかり構築法踏まえて証明する練習をすると、高難易度問題にも繋がりそう！ 問題へのリンク 問題概要 頂点の木が与えられる。 本の辺に対して、なるべく少ない種類の色を用いて色を塗っていきたい。ただし、どの頂点についても、隣接している辺の色がすべて互いに相異なるようにする必要がある。 そのような塗り分け型を実現できるような色の種類の最小値を求め、具体的な塗り分け方を一つ与えよ。 制約 考えたこと 誰もが直感的に思うかもしれない。 次数 (つながる辺の本数) が最大の頂点がボトルネックになる 次数の最大値を d とすると、d 色で塗り… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2020%2F04%2F26%2F172200" title="AtCoder ABC 146 D - Coloring Edges on Tree (2Q, 緑色, 400 点) - けんちょんの競プロ精進記録" 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/d/drken1215/20200426/20200426165726.png Hatena Blog https://hatena.blog 2020-04-26 17:22:00 rich https://drken1215.hatenablog.com/entry/2020/04/26/172200 1.0 100%