トーナメントを二分木で表すと、葉が選手、葉以外の頂点が試合に対応する完全二分木になります。

試合の結果を適当に仮定した場合に問題の解き方を考えます。葉に選手の \(l_i\) を、葉以外の頂点にその試合で負ける選手の \(r_i\) (ただし根は両選手の \(r_i\)) を書くことにします。変更後の \(l_i,r_i\) を \(l_i', r_i'\) とすると、大会を完遂できる条件は \(r_u, l_v\) と書かれた頂点が祖先・子孫の関係にあるすべての \(u, v\) について \(l'_v \leq r'_u\) を満たすことです。また、試合の結果は \(r_i\) が大きい選手を勝たせるのが良いと分かります。

\(l_i' = l_i - x_i, r_i' = r_i + y_i\) と変化させることにします。

• \(\mathrm{minimize} \sum x_i + \sum y_i\)
• \(\mathrm{s.t.}\ x_v + y_u \geq l_v-r_u, x_i\geq 0, y_i\geq 0\)

という線形計画問題は係数行列が全ユニモジュラ行列であるため整数解を持ち、元の問題と一致します。この問題の双対問題は

• \(\mathrm{maximize} \sum (l_v-r_u)z_{u,v}\)
• \(\mathrm{s.t.}\ \sum z_{i,*} \leq 1, \sum z_{*,i} \leq 1, z_{i,j}\geq 0\)

となります。これは \(u, v\) の重みを \(( l_v-r_u)\) とする最大重み二部マッチング問題です。

この問題は二分木上で \(\mathrm{dp}_{i,j}\) を「現在の頂点が \(i\) で、未マッチの \(l_v\) 側の頂点が \(j\) 個であるときの重みの最大値」とし、\(l_v, r_u\) をマッチングに使うと決めたタイミングで \(l_v, -r_u\) を加算するようにすると解くことができます。ここで、未マッチの頂点はその先祖の \(r_u\) としかマッチできず、その個数は高々 \(N+1\) 個なため、\(j\) の範囲は \(N+1\) 以下で良いです。この時点で \(\mathrm{O}(N^2 2^N)\) で解けますが、さらに \(j\) の範囲をその頂点の子孫に存在する葉の個数と \(N+1\) のうち小さい方に制限すると \(\mathrm{O}(N 2^N)\) になります(俗に\(\mathrm{O}(NK)\) の木DPと呼ばれるもの)。