問題
出典 ： https://yukicoder.me/problems/no/1833
題意 ：
$N$ $(2 \leq N)$ 頂点の木が与えられる。高々 $1$ つの単純パスを選び、それに含まれる辺を赤色とし、残りの辺を黒色とする。各辺について定められた次のペナルティの最大値としてありうる最小値を求めよ。ただし、 $C_i$ は与えられ、 $D$ は与えられる $C_i$ のうちの最大値である。
- ペナルティ ： 辺 $i$ が赤色のとき $D-C_i$ 、 黒色のとき $C_i$ 。
解説
概要
とりあえず根付き木にします。
単純パスの端点の lowest common ancestor で場合分けし、木 DP によって葉から次々に求めます。全方位木 DP でもよいですが、代わりに dfs 順序をうまく使う方法を考えます。
木 DP の内容
以下のテーブルの構築が目標です。
- $\text{dp}[v]:={}$ 対象の木が頂点 $v$ の部分木と（存在すれば） $v$ の親だけだったと仮定し、また選ぶパスの端点の片方が今見ている頂点でなければならないとする。このときのペナルティの最大値の最小値。
- $\text{maxC}[v]:={}$ 頂点 $v$ の部分木に含まれる辺と、（存在すれば）$v$ と $v$ の親を結ぶ辺における $C_i$ の最大値。
$v$ から赤い辺を伸ばす方向は、子 $w$ のうち $\text{maxC}[w]$ が最大となるものです。さもなければペナルティは $\text{maxC}[w]$ 以上となり、パスを選ばなくても最小値を達成できてしまいます。
よって、 $\text{dp}[v]$ を、パスを選ばない場合と $w$ 方向のパスを選ぶ場合に分けて計算し、その $\min$ で計算できます。
DP 後、答えを求める
選ぶパスの端点の LCA を $v$ と決め打ったときの答えを定数 $O(c+1)$ ( $c$ は $v$ の子の個数) 時間で求めます。
まず、部分木内から生じるペナルティを最小化します。 $v$ から葉方向にパスを $2$ 方向に伸ばせるので、 $v$ の子 $w$ について $\text{maxC}[w]$ のうち大きいほうから $2$ つを $\text{dp}[w]$ に置き換えて最大値を計算します。これが最適である理由は前述です。
最後に部分木外のペナルティを計算します。頂点を dfs の行きがけ順に並べると $v$ の部分木が区間で表されるので、部分木外はその外側に対応します。この範囲で最大値クエリを処理したいので、行きがけ順の両端からの累積 $\max$ を前計算すれば定数時間になります。
解答例
dfs 順序の設計が面倒なので、代用として heavy-light decomposition を貼りました。
