SRM 578のwriterの一人でした。
rng,tozan,snukeで多摩動物園に行ってそこで問題セットを作ったため、Zooがテーマとなっております。全問題とも３人で共同で作った感じ。
Div1 Hardの解説
概要：木から辺を削除して同形の木を２つ作るとき、作る木のサイズの最大値は？
解法：一応O(N^6)みたいなのでも通るが、ここではO(N^5)を紹介しておく。
・まず辺をひとつ選んで削除し、２つの部分木Aと部分木Bにわける。
・Aに含まれる削除した辺にくっついた頂点を根とし、Bのどの頂点を根にするかを全部試す。
すると根付き木２つから同形の二つの部分木を取る感じの問題になる。
・dp[Aの頂点v][Bの頂点u] = vとuを対応させた時の最大サイズ
・dpテーブルをマージする際に割当問題を解くことになります
この辺の計算量はrngさんに教えてもらったところ Σ deg[u]^2 deg[v] + deg[u] deg[v]^2 = (deg[u1]^2 + deg[u2]^2 + ...)(deg[v1] + deg[v2] + ...) <= N^3 みたいな感じになり、合わせるとO(N^5)やったー。この辺りの計算量解析鮮やかでかっこいい。
