simezi_tan https://blog.hatena.ne.jp/simezi_tan/ simezi_tanの日記 https://simezi-tan.hatenadiary.org/ 動的計画法 グラフ理論 問題 n頂点からなる木がある。木には最初s[i]の値がかかれている。 次の操作をm回行う。 数字tiを手に入れる。捨てるか、好きな木の頂点cを選んで数字を置く。 頂点cにもともとあった数字はcの親に行く。cの親vにあった数字はvの親に行く。 ……と同様に根までこの操作が続けられ、根にもともとあった数字は消える。 最後に木に残っている数字の和を最大化したい。 和の最大値を求めよ。 制約条件 n, m≦5000 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fsimezi-tan.hatenadiary.org%2Fentry%2F20140928%2F1411836450" title="ARC 029 D - 高橋君と木のおもちゃ - simezi_tanの日記" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2014-09-28 01:47:30 rich https://simezi-tan.hatenadiary.org/entry/20140928/1411836450 1.0 100%