CODE THANKS FESTIVAL 2018：G - Sum of Cards
問題
解法
(a_i, b_i) というカードに対して a_i, b_i を頂点として間に辺を張ることを考える．そうすると，いくつかの輪の関係になる．ここでそれぞれの輪は共通の頂点を持ったりしない．
それぞれの輪ごとに数字の種類を決めたときの最大値を求めたい．ここで，各輪に対し以下の DP をする．
dp(i, j, k, l) := i 番目の頂点までで，j 個（種類）選び，i + 1 番目の頂点を選んだかどうかが k であり，1 番目の頂点を選んだかどうかが l であるときの輪の中の最大値
ここで i + 1 番目の頂点を選んだかどうかを状態として持つのは，遷移時に i + 1 番目の頂点を選ぶか i 番目の頂点を選ぶかを試すときに，前者の時種類数 j が変化するかどうかを判断するため．1 番目の頂点に関しても輪になっているので同様の理由で必要．遷移は O(1) で出来，状態数 O(NK) となる．輪一つ一つについて DP を実行するので O(N^2 * K) となりそうだが，複数の輪に属する頂点は存在しないため各頂点は一回しか見ない．なので DP 全体で O(NK + N)．これを全ての輪に対し処理することによって各輪に対して，数字の種類数ごとの最大値を知ることが出来る．
あとはこのデータを用いて以下の DP をする．
dp(i, j) := i 番目の輪までで数字の種類数が j となるように選ぶときの最大値
遷移は各輪で何種類の数字を選ぶかを愚直に試せばよい．遷移 O(N)，状態数 O(NK) となるが，各輪に属する頂点数の合計は N であるのでこの DP 全体では O(NK + N) で済む．全体で O(NK + N)．実装では DP テーブル（メモ化再帰では DP メモ）を各輪ごとに初期化する必要があるが，この初期化を必要な配列の範囲でのみするように最適化しないと TLE になってしまう．また，std::vector などの動的配列であると確実に TLE する．
解答
