木と計算量 前編 〜O(N^2)とO(NK)の木DP〜 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ

この記事はCompetitive Programming Advent Calendar 2018の46日目の記事として書かれました（嘘） 最近、木上のアルゴリズムの面白い計算量解析が２つ話題になったのでまとめておきます。 予備知識 まず、https://web.archive.org/web/20150819082918/https://topcoder.g.hatena.ne.jp/iwiwi/20120428/1335635594 について復習します。 iwiさんのブログとは違う、より直感的な解析方法も紹介します。 以下の問題を考えます。 N 頂点の木が与えられる。 頂点 1 を含む頂点数 K の根付き木の個数を求めよ。 制約：1 ≦ K ≦ N ≦ 3000 典型的な木DPの問題です。 解法は以下の通りです。（解法の細かい説明は本題ではないので追わなくて大丈夫です） 頂点 1 を根