drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ AtCoder AtCoder600点 ARC-C 黄色diff 二乗の木DP 木DP DP 操作 数え上げ問題 操作後の結果の数え上げ 木 グラフ 操作:swap 操作:削除 備忘録として。解説よりもおそらく面倒な DP をした。 問題へのリンク 問題概要 考えたこと 基本的に木 DP のノリで考えることにした。 根を 1 つとったとき、異なる部分木間で交換される頂点はただだか 1 個以内である。そこで次の DP をした。 dp[v][k] ← 頂点 を根とする部分木について、ある時点において根の部分に来ている頂点の個数が 種類であるような操作列によって、出来上がる数列の個数 種類という部分を指定しないと、異なる部分木間の頂点のやりとりの部分で上手く遷移を作れなかった。 計算量は、解法全体を通して二乗の木 DP をすることで となった。 コード #include <… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2024%2F02%2F05%2F021046" title="AtCoder ARC 171 C - Swap on Tree (黄色, 600 点) - けんちょんの競プロ精進記録" 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/1687765056723440 Hatena Blog https://hatena.blog 2024-02-05 02:10:46 rich https://drken1215.hatenablog.com/entry/2024/02/05/021046 1.0 100%