AtCoder Beginner Contest 259 F問題 Select Edges

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

$N$ 頂点の木 $T$ がある. $i$ 番目の辺は頂点 $u_i$ と頂点 $v_i$ を重み $w_i$ で結ぶ.

以下を満たす $T$ の全域部分グラフ $T'$ のうち, $T'$ にある辺の重みの総和の最大値を求めよ.

各頂点 $i=1,2, \dots, N$ に対して, $T'$ における頂点 $i$ の次数は $d_i$ 以下である.

制約

$2 \leq N \leq 3 \times 10^5$
$1 \leq u_i, v_i \leq N$
$-10^9 \leq w_i \leq 10^9$
$d_i$ は $T$ における頂点 $i$ の次数以下の非負整数.
$T$ は木

解法

$T$ を適当な頂点 ${\rm root}$ に対して根付ける. そして, 木 DP で解くことにする. 具体的には, ${\rm DP}[v,j]~(1 \leq v \leq N, 0 \leq j \leq d_v)$ を以下の値とする.

頂点 $u$ を根とする部分根付き木に問題を制限したとき, 頂点 $u$ の次数が $j$ であるような全域部分グラフにおける辺の重みの最大値 (存在しない場合は $-\infty$ ).

この値を葉から求めていく. 頂点 $u$ が葉であるとき, 頂点 $u$ を根とする部分根付き木は頂点 $u$ のみからなるグラフである. よって,

${\rm DP}[u,0]=0$
$d_u=1$ であるとき, ${\rm DP}[u,1]=-\infty$

である.

頂点 $u$ の子全体の集合を ${\rm ch}(u)$ とする. このとき, $v \in {\rm ch}(u)$ として,

辺 $uv$ を採用しないならば, 頂点 $u$ を根とする部分根付き木の部分については $\displaystyle \max_{0 \leq j \leq d_v} {\rm DP}[v,j]$ を達成するように辺を選べばよい.
辺 $uv$ を採用するならば, 頂点 $u$ を根とする部分根付き木の部分については $\displaystyle \max_{0 \leq j \lt d_v} {\rm DP}[v,j]$ を達成するように辺を選べばよい.

$\displaystyle \alpha_v:=\max_{0 \leq j \lt d_v} {\rm DP}[v,j] , \beta_v:=\max_{0 \leq j \leq d_v} {\rm DP}[v,j]$ とすると, $\alpha_v=\max(\beta_v, {\rm DP}[v, d_v ])$ である. すると, 各 ${\rm DP}[v, j]$ は次の問題の答えになる. ただし, 辺 $uv$ が $i$ 番目の辺であるとき, $w_i$ のことを $w_{uv}$ と書くことにする.

$\operatorname{ch}(u)$ の分割 $\operatorname{ch}(u)=X \coprod Y$ で $\left|Y \right|=j$ となるような分割における

$\displaystyle \sum_{v \in X} \alpha_v+\sum_{v \in Y} (\beta_v+w_{uv})$

の最大値を求めよ.

この問題の答え ${\rm DP}[v, j]$ は $\delta_{u,v}:=(\beta_v+w_{uv})-\alpha_v$ として, $\Delta_u=\left(\delta_{u,v} \right)_{v \in \operatorname{ch}(u)}$ を昇順に並べた列を $\widetilde{\Delta_u}=\left(\widetilde{\delta_u}_k \right)_{1 \leq k \leq \left|\operatorname{ch}(u) \right|}$ としたとき,