ABC 369 G — As far as possible

考察

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.

出典

分類・前提・執筆情報

掲載状態: 収録済み

As far as possible の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 分離凸・凹の単調限界値選択

主題
  • 分離凸・凹の単調限界値選択: 分離凸費用または分離凹利益を単調な限界値列へ分解し、heap mergeか閾値別の個数・総和により必要な上位・下位K項を選べる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: 分離凸・凹の単調限界値選択

    補助タグ: 根付き木DP・部分木集約

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

    学習の位置

    体系上の位置: 分離凸・凹の単調限界値選択

    • 分離凸費用または分離凹利益を単調な限界値列へ分解し、heap mergeか閾値別の個数・総和により必要な上位・下位K項を選べる。

    先に読む単元:

    • 一次元凸・単峰最適化 — 差分/導関数の単調性または単峰性を証明し、連続解近傍・ternary search・整数境界で最適点を求める。その発動条件と正当化原理を比較可能な独立教材として学ぶ。
    • 根付き木DP・部分木集約 — DPの最小十分状態で得た考え方と実装を再利用し、根付き木DP・部分木集約の発動条件・正当化・境界を重複なく学ぶ。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題