今回扱うのはyukicoder contest 484 E問題 No.3283 Labyrinth and Friendsです。公式解説に載っていない別解を紹介します。

問題の概要

正確な問題文はこちらです。

$N$頂点根付き木$T$の各頂点$v$に非負整数値価値$s_v$が、各辺$e$に非負整数値コスト$c_e$が定義されている。根を含み価値の総和が$X$以上となる連結誘導部分グラフのコストの総和の最小値を求めよ。

前置き

公式解説で扱われている解法は二乗の木DPと呼ばれるテクニックの亜種のようですが、二乗の木DPは少なくともここ3年以内に★3以下でyukicoderで要求されたことがなく（集計を間違っていたらすみません）、主に★3以下までしかupsolveしていない筆者（$p$進大好きbot）は二乗の木DPを名前しか聞いたことがありませんでした。

となるとこの問題の難易度（★2.5）が主戦場の他の参加者も知らない可能性があると思ったので、二乗の木DPを一切使わない解法を紹介すると役に立つかもしれないと思い、深さ優先探索を用いたナップサックDPを紹介します。

準備

まず根付き木などの有向非輪状グラフ（DAG）で何かを計算する問題は、線形グラフの場合に絞って考察をし、それを一般化できるかを考えると良いです。

今回は線形グラフだと始切片（一般の部分集合ではなく始端を端点とする区間）のみ選択可能なナップサック問題となり、「始端から頂点$v$までをちょうど選択する場合の価値とコスト」を累積和の容量で計算していくだけで解くことができます。一本道ですからね。

根付き木への一般化を見据えてあえてナップサックDPに拡張すると、$\textrm{dp}[v][x]$に「始端から頂点$v$までをちょうど選択する場合に価値$x$以上を実現するコストの下限（実現できない場合は$\infty$）」を格納していくという方法が思いつきます。（実装上は$x < X$において「価値$x$以上」を「価値$x$」に置き換えても構いません）

そこで同様のナップサックDPを一般の根付き木に拡張できるか考えてみます。ナップサックDPでは線形グラフの始端から終端まで順に頂点を訪問しながら計算をしていました。その訪問順を一般の根付き木に拡張する手段の１つは、深さ優先探索の訪問順です。

というわけで、$N$以下の各正整数$i$に対し、深さ優先探索で$i$番目に訪問する頂点に名前をつけて$v_i$と置くことにします。また線形グラフにおける始切片の対応物として、$v_1,\ldots,v_i$を頂点集合に持つ$T$の誘導部分グラフである木を$T_i$と置くことにします。

解説

線形グラフの時はDP配列のパラメータ$v$が「グラフをどう打ち切るか（始切片情報）」と「どの頂点を選択するか（頂点情報）」の$2$つの情報を兼ねていましたが、一般の根付き木は一本道ではないので更に冗長に$1$パラメータ増やして$\textrm{dp}[i][v][x]$に「$T$を$T_i$に置き換えた問題において$T_i$の頂点$v$を選択する際に価値$x$以上を実現する場合のコスト最小値」を管理することにしましょう。最終的な答えは$\textrm{dp}[N][v_1][X]$です。

そして漸化式を立ててみようと思うと$T$において$v$が$v_i$の祖先（$v_i$含む）でない時に$\textrm{dp}[i][v][x]$の更新が簡単にはいかなくて、考察ミスをしたり詰まったり大変な思いをします。

それはさておき求めたい値は$\textrm{dp}[N][v_1][X]$でした。その計算過程で参照される値を絞り込んでみると結局$v_i$の祖先であるような$v$に対する$\textrm{dp}[i][v][x]$しか参照されないことが分かります。

というわけで$v_i$の祖先である$v$に絞ると以下のような動的計画法で$\textrm{dp}[i][v][x]$を求めることが可能です。

1. $i = 1$ならば$v = v_1$に限られ、$\textrm{dp}[i][v][x]$は
   1. $x = 0$ならば$0$と定める。
   2. $x > 0$ならば$\infty$と定める。
2. $i > 1$ならば$v$は$v_i$の祖先に限られ、$\textrm{dp}[i][v][x]$は
   1. $v = v_i$ならば$T$における$v$の親を$p$として、$\textrm{dp}[i-1][v][x]$と$\textrm{dp}[i-1][p]$から線形グラフのナップサックDPと同様の漸化式で定める。つまり以下のように処理する。
      1. $x \geq s_p$ならば$\min(\textrm{dp}[i-1][v][x],\textrm{dp}[i-1][p][x-s_p]+c_{p \to v})$と定める。
      2. $x < s_p$ならば$\textrm{dp}[i-1][v][x]$と定める。
   2. $v \neq v_i$ならば$v_i$を$T_i$の根とした時の$T_i$における$v$の親を$p$として$\min(\textrm{dp}[i-1][v][x],\textrm{dp}[i][p][x])$と定める。

さて立式のために$i$というパラメータを設けたものの、上の漸化式を見る限り$i$は不要な（inplace化できる）ので$\textrm{dp}[i][v][x]$の代わりに$\textrm{dp}[v][x]$として管理すれば良いです。

というわけで上の動的計画法をinplaceで計算することにすると、結局次のような手順になります。

1. $\textrm{dp}[v_1]$を$(0,\infty,\ldots)$と定める。
2. 深さ優先探索を行い、
   1. 頂点$v$から子ノード$c$に進む時は$\textrm{dp}[c]$を$\textrm{dp}[v]$から線形グラフのナップサックDPと同様の漸化式で定める。
   2. 子ノード$c$から頂点$v$に戻る際は$\textrm{dp}[v]$を$\textrm{dp}[c]$で成分ごとにchange min更新する。

これは単純な再帰で実装可能です。この解法の計算量は想定している実装において$\Theta(NX)$です。

感想

考察部分は★3のF問題以上に苦戦しました（F問題はライブラリがバグってて実装で苦戦したわけですが）。

二乗の木DPを知っている人なら★2.5と同レベルに感じるのかな？

実装例

• c++: https://yukicoder.me/submissions/1123329

自分用覚え書き

github pagesで数式を使う際は、閉じカッコと半角アンダーバーの間に半角スラッシュを入れないとmarkdownからhtmlへの翻訳の仕様でバグるらしい。

数式環境をくくる大括弧と数式環境内の中括弧や半角空白や濃度のシャープは半角スラッシュ２つ、改行は半角スラッシュ５つ、その他は基本的に半角スラッシュ１つで良さそう。htmlとmathjaxの関係が難しい。

inline数式内の縦棒はlvertなどを使わないとmarkdownの表と認識される。

arrayとalignはどちらも使える。arrayが使えない気がしてしまったのは中括弧につける半角スラッシュの個数を間違えていたから。alignはアンパサンドを等号の右側につけて半角空白を２つ入れると幅がちょうど良さそう。arrayなしだとアンパサンドは使えない。