emtubasa https://blog.hatena.ne.jp/emtubasa/ ツバサの備忘録 https://emtubasa.hateblo.jp/ 全方位木dp 動的計画法(DP) 前計算 問題 提出コード 解法 全方位木dpをします。 初めに頂点1が根である際の値を求めます。 を根とする部分木について、を黒で塗った際の部分木の塗り方 とすると、頂点の子の集合をとして、 となります。 を根とした際の求めるべき答え とすると、 となります。 が求まっている際に、その子であるについての答えを求めるため、へシフトすることを考えます。 書き換えるべき場所は、とのみになります。 については、定義に基づいて計算すればよいので、を求めることのみ考えます。 となるので、あとはこれを計算すればよいのですが、愚直に計算をすると間に合いません。 ある数列について、を高速に計算する方法を考えます。 これ… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Femtubasa.hateblo.jp%2Fentry%2F2019%2F11%2F15%2F141626" title="Educational DP Contest / DP まとめコンテスト V - Subtree - ツバサの備忘録" 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.blog.st-hatena.com/images/theme/og-image-1500.png Hatena Blog https://hatena.blog 2019-11-15 14:16:26 rich https://emtubasa.hateblo.jp/entry/2019/11/15/141626 1.0 100%