AOJ 2611 - 順位付け - ツバサの備忘録

解法

木の2乗DPとかなんとか言われてるやつです。
問題文をじっくり読むと、入力が木になっていて、そのなかで順位付けをしていくことがわかります。木全体の根は、入力時点で一番高さが高かった頂点です。
木の高さがすべて異なる場合は簡単に求めることができますが、同じ高さの場合があるのでさっと解くことはできません。
以下のようなDPを考えます。

$dp[v][i] = v$ を根とする部分木について、高さの種類数が $i$ となるようにしたときの、高さの決め方

頂点が葉だった場合は、 $dp[v][1] = 1$ となります。
それ以外の場合、子についてそれぞれ探索してから、自分自身にマージしていくことを考えます。
$tmp[i] =$ 子についていくつか見た後の、現時点での値(高さが $i$ 種類となるようなパターン数)
ここに、 $dp[c][j]$ 達をマージしていきます。 $c$ は、今見ている子です。
$tmp[i]$ と $dp[c][j]$ を組み合わせると、
新たな種類数は $[max(i,j) , i + j]$ の区間のいずれかの値になります。
新たな種類数が $k$ になるパターンを考えます。
$i,j$ 種類を組み合わせて $k$ 種類にする際、

$k$ 種類の中から、 $i$ 個を選び、 $tmp$ 側の高さを全て割り振る

という操作をまず行うと、 $k$ 種類の中から、すでに選択された $i$ 個と、まだ選択されていない $k-i$ 個にわかれます。
ここから、 $j$ 個の頂点に高さを割り当てなければなりませんが、この中で、 $k-i$ 個は残りの $j$ 個のいずれかが選ばないといけないので無視します。
ということで、残った $i$ 個の中から、 $j - (k - i)$ 個を選び、 $j$ に割り当てる必要があります。
割り振る場所を決めてしまうと、順番は一意に決まるので、最終的に、 $i,j$ 種類を組み合わせて $k$ 種類を作成する際のパターン数は、
$_{k}C_{i} \times _{i}C_{(i + j - k)}$ 通りです。
ということで、ここに $tmp[i] \times dp[c][j]$ をかけたものを、新たに足しこめばよいです。
f:id:emtubasa:20200501143824j:plain
このようにして、 $tmp$ と $dp[c]$ を組み合わせて新たな $tmp$ を作成、という操作を繰り返します。
その後、最終的な $tmp$ について、 $dp[v][i] = tmp[i - 1]$ とすればよいです。今見ている頂点 $v$ 自身を種類数に加えるためです。
計算量についてですが、一見 $O(N^{4})$ かかるように見えますが、一番内側のループ以外が合わせて $O(N^{2})$ になるみたいです。
詳しい解析はこちらを参照してください。

snuke.hatenablog.com