Livedoorブログからの移動
はてなブログからの移動

E - Bichrome Tree

解き方

  • ある頂点iの部分木について、黒白それぞれの重みの和を、b_i, w_iとして、それを更新していく
    • 黒白は入れ替えても問題ないので、違う色か同じ色かだけ考えれば良い
  • 頂点iがleafの場合、色はどちらでもよく、重みはx_iになる
  • 頂点iがleafでない場合
    • 子どもの重みの割当b, wをそれぞれまず計算する
    • iへ色と重みを割り当てると、b_i = x_iまたはw_i = x_iを満たすが、ここでx_iでない方はできるだけ小さい方がその後の重み割当がしやすくなる
      • 頂点iの子どものリストをc_1, c_2, ..., c_nとして、dp[j][k] = c_1, ... c_iまでを使って、重みの和がjになるような色の割り当て方があるかどうか(true, false)と定義してDP
      • dp[n][k] = trueとなる最大のkを用いてiへの色の割当を考える
  • 計算量の見積もり（怪しい）
    • DPについて: k <= X_iとして問題なく、さらに各辺について、1回しかこのDPで参照されないので、解法全体を通してO(NX)で収まるはず
    • dp[n][k] = trueなる最大のkを求める：O(X)
      • これは各頂点について行われるので、解法全体でO(NX)
    • 解法全体ではO(NX)のはず

github.com