AtCoder Beginner Contest 222 F 問題 Expensive Expense

問題

提出解答

問題の概要

$N$ 頂点からなる重み付き木がある. それぞれの辺は $A_i, B_i$ を結び, 重みは $C_i$ である. そして, 各頂点には整数 $D_i$ が指定されている. $E_{i,j}$ を $i, j$ 最短路の重みと $D_j$ の和とする. このとき, $i=1, \dots, N$ に対して, 以下の値を求めよ.

$\displaystyle \max_{\substack{j=1, \dots, N \\ j \neq i}} E_{i,j}$

制約

$2 \leq N \leq 2 \times 10^5$
$1 \leq A_i, B_i \leq N$
$1 \leq C_i \leq 10^9$
$1 \leq D_i \leq 10^9$

解法

全方位木DPで解くことにする. 木 $T=(V,E)$ とし, ある頂点を根とする木DP において, 更新式が以下のような式で表せるとき, 筆者が抽象化したものを使うことができる. ただし, ${\rm ch}(v)$ で頂点 $v$ の子の全体の集合とする.

$\displaystyle {\rm DP}[v]=g\left(\bigodot_{w \in {\rm ch}(v)} f({\rm DP}(w), v,w) ,v\right)$

ただし, $(M, \odot)$ を可換モノイド, $X$ を集合とし, $f: X \times V \times V \to M, g: M \times V \to X$ とする. ただし, $f$ については, $v,w \in V$ で, $v$ が $w$ 親のときのみ定まっていれば十分である.

この問題においては以下のように定めるとうまくいく. ただし, $vw \in E$ のとき, 辺 $vw$ の重みを $\operatorname{cost}(v,w)$ とする. このとき, $\operatorname{cost}(v,w)=\operatorname{cost}(w,v)$ である.

$M=\mathbb{N}$ (非負整数全体の集合)
$x,y \in M$ に対して, $x \odot y:=\max(x,y)$
$(M, \odot)$ の単位元は $0$ である.
$f(x,v,w):=\max(x+\operatorname{cost}(v,w), D_w+\operatorname{cost}(v,w))=\max(x, D_w)+\operatorname{cost}(v,w)$
$g(x,v):=x$

(考え方) ${\rm DP}(v)$ で, 問題を $v$ を根とする部分木に制限した場合の答えとする. ${\rm ch}(v)=\{w_1, \dots, w_r\}$ とする. $v$ とは一致しない $v$ の子孫 $u$ において, 以下のように考える.

$u \in \{w_1, \dots, w_r \}$ のとき: $E_{v,u}=D_u+\operatorname{cost}(v,u)$ である.
$u \not \in \{w_1, \dots, w_r \}$ のとき: $u$ は頂点 $w_j$ を根とする部分木内の頂点とする. このとき, $E_{v,u}=\operatorname{cost}(v,w_j)+E_{w_j, u}$ である.

よって,

$\begin{align} {\rm DP}(v) &=\max_{\substack{u \in {\rm ch}(v)\\ u \neq v} } E_{v,u} \\ &=\max_{j=1, \dots, r} \left(\max_{u \in {\rm ch}(v)} E_{v,u} \right) \\ &=\max_{j=1, \dots, r} \left(\max \left(D_{w_j}+\operatorname{cost}(v,w_j), \max_{\substack{u \in {\rm ch}(w_j) \\ u \neq w_j}} (\operatorname{cost}(v,w_j)+E_{w_j, u}) \right) \right) \\ &=\max_{j=1, \dots, r} \left(\max \left(D_{w_j}, \max_{\substack{u \in {\rm ch}(w_j) \\ u \neq w_j}} E_{w_j, u} \right)+\operatorname{cost}(v,w_j) \right) \\ &=\max_{j=1, \dots, r} \left(\max \left(D_{w_j}, {\rm DP}(w_j) \right)+\operatorname{cost}(v,w_j) \right) \end{align}$