ABC 222 E — Red and Blue Tree

考察

色を決める前から駒が通る道は木の一意な単純路で確定しているため、各辺が何回使われるかだけを先に数えれば、移動列そのものは以後の判定に不要になる。S=ΣC_e とおくと R+B=S なので、R-B=K は赤い辺に対応する C_e の和が (S+K)/2 であることと同値になる。S+K が奇数、または目標和が 0 未満・S より大きい場合は不可能であり、C_e=0 の辺も二つの色を別の選択としてDPに通す必要がある。

採用する候補: 連続する A_i,A_{i+1} 間のパスから各辺の通過回数 C_e を求め、赤にする辺の通過回数の和を数える部分和DPへ変換する。

色の寄与が辺ごとの C_e に分離し、R-B=K を一つの部分和条件へ直せるため、2^(N-1) 通りの彩色を列挙せずに数えられる。

棄却する候補: 全ての辺の赤青を列挙し、各彩色について移動列を再現して R-B を調べる。

辺数に対して指数個の彩色があり、N=1000 では列挙できないうえ、同じ辺を通る移動を何度も評価してしまう。

各 A_i から A_{i+1} への木上パスをDFSで復元して C_e を加算し、目標 (S+K)/2 に対して C_e を一度ずつ選ぶ0/1部分和DPを行う。

典型の発動条件

木上パスの辺使用回数への圧縮

発動条件: 木上の複数の移動に対し、最終評価が各辺を通った回数と辺属性だけで決まるとき。

一意なパスごとに辺カウンタを加算し、長い移動列を N-1 個の独立な辺の重み C_e へ縮約する。

符号割当てから部分和DPへの変換

発動条件: 各要素を正負のどちらかへ割り当て、その符号付き総和を指定値にしたいとき。

総和 S と符号差 K から正側の和を (S+K)/2 と定め、各 C_e を選ぶかどうかの数え上げにする。

問題固有の要素

辺の色は全移動で共通でも、色が答えに与える影響は『その辺の総通過回数』だけなので、時系列と彩色を分離できる。

別の問題へ持ち帰る視点: 同じ選択が多数のイベントへ繰り返し作用するときは、イベントを再生する代わりに選択対象ごとの使用回数を集計する。

正当性

木pathは一意なので各辺の通過Cが確定する。赤寄与R、青寄与BについてR+B=S,R−B=KよりR=(S+K)/2。赤辺subsetをこの和で数えることは彩色と一対一。負・奇数・範囲外目標なら不可能。

実装上の注意

  • S+K の偶奇と目標和の範囲をDP前に検査し、C_e=0 でも『赤にする・青にする』の二遷移を残す。

復習の核

  • 『正側の和−負側の和』を見たら、まず全体和との連立で片側の和を決められないか確認する。

計算量と制約

時間

N頂点、訪問列長M、全通過回数S。各path DFS O(NM)、0/1 DP O(NS)。

空間

木、辺回数 O(N)、和DP O(S)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 1000; 2 \leq M \leq 100; |K| \leq 10^5; 1 \leq A_i \leq N; 1\leq U_i,V_i\leq N; The given graph is a tree.; All values in input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Red and Blue Tree の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 資源・容量DP

主題
  • 資源・容量DP: 資源軸の上限と更新順を選び、選択の重複を避けられる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: 資源軸knapsack DP

    補助タグ: 寄与の数え上げと順序交換

    執筆: abc-explanation-author1.1.1 / revision 2

    学習の位置

    体系上の位置: 資源・容量DP

    • 資源軸の上限と更新順を選び、選択の重複を避けられる。

    先に読む単元:

    この解説で扱わないこと:

    • 使用済み要素集合そのものを状態とし、容量・個数の値軸を持たないDP。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題