drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ Codeforces EducationalCodeforces マージテク 木 グラフ 各kに対して 木DP 最頻値に関する問題 色に関する問題 最適解の数え上げ CodeforcesR2300 【問題集】木DPのステップアップ マージテク童貞を卒業した！！！ 問題へのリンク 問題概要 頂点の根付き木が与えられる (根の番号は 1)。また各頂点 には色 が塗られている。色は整数値で表される。各頂点 について、以下の問いに答えよ。 その頂点を根とした部分木を考える その部分木で「最頻出の色」をすべて求める その最頻出の色の表す整数値の合計値を求めよ。 制約 考えたこと 一見するとナイーブな木 DP で かかるように思えてしまうけど、マージテクによって計算量が下がるという教育的問題！！！ 各部分木について どの色が何個あるかを表す counter (map で実装) 最頻値がいくつか mean 最頻値な色の総和 sum を… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2020%2F02%2F02%2F012600" title="Educational Codeforces Round 2 E. Lomsat gelral (R2300) - けんちょんの競プロ精進記録" 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.user.blog.st-hatena.com/default_entry_og_image/80936665/1516148889515660 Hatena Blog https://hatena.blog 2020-02-02 01:26:00 rich https://drken1215.hatenablog.com/entry/2020/02/02/012600 1.0 100%