Succession (UVa Live Archive Asia Amritapuri 2009)

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=345&page=show_problem&problem=2686

問題

各頂点に点数が書かれていている頂点数Nの木がある。連結なK個の頂点の得点の合計の最大値とそのような頂点の選び方の個数を答える問題。
1<=K<=N<=100

解法

DPで解く。dp[i][j]は頂点iを使ってかつi以下の連結した頂点をj個使った場合の最大得点とし、cnt[i][j]はそのようになる点の選び方とする。
dp[i][j]とcnt[i][j]はその子供が高々2つの時、O(K^2)で簡単に求めることができる。m個の子供を持つ場合は先に二つの子供をマージすることにより、m-1個の子供にすることが出来る。
マージの回数は高々N回なので全体のオーダーはO(NK^2)となる。