Codeforces darkshadows's blog 「DP on Trees Tutorial」Problem 5

Codeforces darkshadows's blog 「DP on Trees Tutorial」Problem 4の続編です。
codeforces.com

問題５．
「頂点1を根を持つ二つの木T1, T2が与えられます。T1とT2を同じ構造にするために、足りない葉をそれぞれの木に補います。葉となる頂点を一つ補うたびにコストが1かかるとき、必要なコストの最小値を求めてください。」

少し問題設定が分かりにくいかもしれません。下図を見てください。

このように、T1とT2を同じ構造にするためにはT1に赤い頂点を1つ、T2に青い頂点を3つ追加する必要があり、
必要となるコストの最小値は 1+3=4 と計算できます。このとき、根の方向に頂点を追加することはできないことに注意してください。

さて、T1とT2を同じ構造にするとき、最小コストはどのように計算できるでしょうか？
「根の方向に頂点を追加することができない」ことから、新たに頂点を追加してもT1の根は頂点1、T2の根は頂点1ということで変わりませんね。
T1の頂点1の子をu1, u2, ... ,un、T2の頂点1の子をv1, v2, ... , vmとします（簡単のため、n>mとしておきます）。

すると、T1の子uiにT2の子vjを割り当てたときの最小コストをC(ui, vj)と定義すれば、割り当て方を決めたとき、

C(1, 1)=min( ∑C(ui, vj) )　・・・（＊）

と計算することができますね。

このときn>mなので、T2の頂点1の子にv(m+1), ... , v(n)を追加しておきます。
ただ、これらは本来存在しないため、例えばT1の頂点uiにT2の頂点vj ( m+1<=j<=n )を割り当てたときのコストは、部分木uiのサイズとなります（その分だけT2に頂点を追加すればよいです）。これは前もってO(N)で計算できます（厳密ではありませんが、ここでいうNはmax(T1のサイズ, T2のサイズ)としておきます）。

また、T1の頂点uiにT2の頂点vj ( 1<=j<=m )を割り当てたときの最小コストは、uiの子の頂点にvjの子の頂点を割り当てる同様の方法で再帰的に計算できます。

u1, u2, ... , unにv1, v2, ... , vmを割り当てるときの最小コストを求める問題は「割り当て問題」という名前がついており、
ハンガリアン法を用いてO(N^3)で計算できます。

このときにコスト行列というものを用います。コスト行列の説明、ハンガリアン法の実装は以下のリンクを参考にしてください。

コスト行列の説明：
http://www.tcp-ip.or.jp/~n01/math/cost.pdf

ハンガリアン法の実装：
ei1333.github.io

根の方向に頂点を追加することはできないため、C(1, 1)を再帰的に計算する際は、T1の頂点iについて子の頂点がu1, u2, ... , unのとき、相手となるT2の頂点jが決まっており、その子の頂点v1, v2, ... , vmを割り当てることになります。

そのため、ハンガリアン法を用いた計算は高々N回行えば十分であり、計算量はO(N^4)となります。
（実装略）