考察
Aokiが選んだ頂点を全て含む根1からの最小部分木を往復するのがTakahashiの最短walkで、scoreはその部分木の辺重み和の2倍になる。
部分木T_uのK別最適値S_u(K)の差分列は非増加になる。子vへの辺では最初の一頂点を選ぶ限界利得だけが2L+S_v(1)へ増え、以後の限界利得は子の差分を引き継ぐ。
採用する候補: DFSで各子の第一限界利得に辺往復分を足し、頂点ごとに最大一つを親へ残して他と0をglobal multisetへ集める。
非増加な限界利得列のmergeとして木DPを表し、全Kの値を一つのsorted multisetのprefix和へ圧縮できる。
棄却する候補: 各頂点uでKごとのknapsack DPを子部分木サイズに沿ってmergeする。
定義どおりだが全頂点の部分木サイズを掛け合わせる二次的処理になり、限界利得のconcavityを使えていない。
子vから一頂点以上選ぶと辺(u,v)を必ず往復するため、子列の先頭だけへ2Lを加える。各子列が非増加なら全列から大きい順に限界利得を取るのが最適である。
u自身を選ぶ選択肢の限界利得は0であり、K=|T_u|ではuを追加してもscoreが増えないというS_u(last)=S_u(last−1)を表す。
葉はbest=0を返す。内部uでは各子vからcandidate=best_v+2L_{uv}を得て最大一つをbest_uとして親へ返し、残りcandidateとu自身分の0をglobal配列へ追加する。rootのbestとglobal配列を合わせて降順限界利得列を作り、そのprefix sumをK=1..Nの答えとして出力する。
典型の発動条件
concave tree DPの限界利得merge
発動条件: 子ごとの選択数DPが離散concaveで、合計選択数を配分するとき。
値列でなく非増加差分列をmergeして上位K個を取る。
最大要素だけのsmall-to-large圧縮
発動条件: 各nodeで子列先頭の最大一つだけが親の先頭へ連鎖するとき。
最大candidateを返し、確定した他のmarginalをglobal multisetへ退避する。
問題固有の要素
各辺の往復価値は、その子部分木から最初の一頂点を選ぶ瞬間だけ発生する固定bonusとして限界利得へ載る。
別の問題へ持ち帰る視点: subset活性化costがある資源配分では、各groupのfirst marginalだけを修正して差分列をmergeする。
正当性
選択頂点を含む根部分木の各辺は最短walkで往復するのでscoreは辺和の2倍。子へ一頂点でも選ぶ初回だけ辺重み2Lが付くため、子の非増加限界列の先頭へ足す。独立な子列の上位K項を選ぶとprefix条件が自動的に守られ最適。最大先頭だけ親へ返し他をglobalへ出す分解はこのmergeの全項を保存し、最終prefix和が全Kの最適値になる。
実装上の注意
- scoreは往復なので辺長を2倍する。各内部頂点につき0を一つだけ追加し、最終限界利得数がN個になることをassertする。
復習の核
- 葉・chain・starで返すbestとglobalへ置く値を手計算する。S(K)差分が非増加という帰納と0追加の意味を説明する。
計算量と制約
時間
O(N log N)。tree差分の分解と全限界利得sort。
空間
O(N)。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2\leq N\leq 2\times 10^5; 1\leq U_i<V_i\leq N; 1\leq L_i\leq 10^9; All input values are integers.; The given graph is a tree.
出典