考察
白pathを最大K回塗る操作の最終結果は、treeから高々K本のvertex-disjoint pathを選ぶことと同値である。pathの順序は結果に影響しない。rooted subtreeをparentへ接続できる情報として、root未選択、root選択で子への選択辺次数0・1・2の計四状態を区別すればchildをknapsack mergeできる。vertex vを単独で選ぶ状態をweight A_v・path数1のopen componentとして初期化し、child endpointと一回結べばvはendpoint、二回結べば内部になり、それ以上は接続できない。edgeを使わずchildの解を並置する遷移ではpath数を足し、edgeで二open componentを結ぶ遷移ではpath数を足して1引く。このcomponent数管理が操作回数に一致する。
採用する候補: 選択path数kとrootの接続statusを持つtree DPを、各childについてO(K^2)でmergeする
child側のroot endpointと現在rootのopen pathをedgeで結ぶと二componentが一pathへmergeされ、path数が1減る。root degreeは最大2なのでvertex-disjoint path条件を局所的に保てる。
棄却する候補: pathの端点pairを全て列挙し、重ならない最大K本の組合せを探索する
tree上にもΘ(N^2)本のpathがあり、その集合packingを直接扱えない。Kが小さいことはsubtree DPのcount軸に使うべきである。
このcomponent数管理が操作回数に一致する。
treeをroot化し、各vで未選択/v選択で子向き次数0/1/2の配列dp[status][k]を初期化する。childの同配列と、edge不使用の並置または両endpoint接続を全k分割でmergeし、vの次数0..2を更新する。rootで全status・k≤Kの最大を取る。
典型の発動条件
tree knapsack
発動条件: 各subtreeから選ぶcomponent数に小さい上限Kがあり、child解を分配して併合するとき。
path数kを軸にchildごとO(K^2) mergeする。
open/closed component DP
発動条件: subtree境界のrootを介して選択構造がparentへ延長される可能性を区別するとき。
未選択と、選択済みの子向き次数0・1・2を別状態にする。次数0と1はいずれも親へ接続できるが、さらに子を何本接続できるかが異なる。
vertex-disjoint path packing
発動条件: tree上でdegree≤2の選択forestを最大重み化するとき。
選択頂点の局所degreeを0..2に制限し、component数をpath本数として数える。
問題固有の要素
path本体を保存せず、subtree境界で外へ接続できるendpointがvにあるかだけを伝えると、重なり禁止を局所mergeで保証できる。
別の問題へ持ち帰る視点: tree上の連結部分構造packingでは、parent edgeを通じて未完構造が何本出られるかをboundary stateに圧縮する。
正当性
選択辺のdegree≤2を保つforestはvertex-disjoint path集合。未選択、root選択でdegree0/1/2という境界状態とcomponent数が親との結合に十分。childとedgeで結ぶと二componentが一つになるので数−1、結ばなければ加算。全選択forestを子分解で一意に覆い重み最大を得る。
実装上の注意
- 次数0と1を同じopen状態へ潰さない。次数0にはさらに子二本、次数1には子一本だけ接続できる。
- edge接続は親側次数0/1、子側次数0/1でのみ許し、親側の次数を一つ増やす。非接続は全状態間で可能。不可能状態は−∞、空選択は0、単頂点pathは(A_v,1,次数0)で初期化する。
- merge後k>Kの状態は捨てられる。非接続ならkは加算、接続では両側が少なくとも1componentなので結果kは各入力のk以上であり、以後のmergeでも減らせない。
- 重みは64bitを使い、深い木は反復的な帰りがけ順で処理する。
復習の核
- K=1、star中心を使うpath、chainで複数区間、単頂点pathが最適な小treeを全path subset列挙と比較する。
計算量と制約
時間
N頂点、path数上限K。各child knapsack素朴merge O(NK²)。
空間
全頂点status×countを保存するなら O(NK)、child解放可能。
制約との対応
公式制約の確認範囲: Time limit: 3 sec; Memory limit: 1024 MiB; Constraints: 2\le N\le 2\times 10^5; 1\le K\le 5; 1\le A_i\le 10^9; 1\le U_i < V_i \le N; The given graph is a tree.; All input values are integers.
出典