問題
根付き木があり、頂点 $0,\dots,N-1$ 、頂点 $v$ の親を $\mathrm{par}(v)$（根は親なし）とする。各頂点に目標値 $t_v$ が与えられる。整数値 $a_v$ を各頂点に割り当て、以下を満たすようにしたい。
- 制約: 根以外の全頂点 $v$ について $a_v \le a_{\mathrm{par}(v)}$（親は子以上）
- 目的: $\displaystyle\sum_v |a_v - t_v|$ を最小化
この最小値を求めよ（直線上の「非減少列への最小コスト変換」の木への一般化）。
入力形式
N
par_1 ... par_{N-1}
t_0 ... t_{N-1}制約
$1 \le N \le 2\times10^4$
$0 \le \mathrm{par}(v) < v$
$-10^9 \le t_v \le 10^9$
入出力例
入力例1（鎖）
5
0 1 2 3
5 1 9 2 8出力例1
14入力例2（分岐木）
6
0 0 0 1 1
4 9 1 7 2 10出力例2
6概念図：子のL-heapのみをmergeし、R-heapは捨てる
ヒント（段階的開示）
ヒント1（方向性）
$a_v \le a_{\mathrm{par}(v)}$ という制約は、直線上の「単調非減少列」問題の親子版だと考える。Slope Trick（凸区分線形関数を2つのヒープで表す技法）を使う。
ヒント2（アプローチ）
頂点 $v$ を根とする部分木で「$a_v=x$ に固定したときの最小コスト」を凸関数 $F_v(x)$ とする。子 $c$ が親に渡せる情報は $G_c(x)=\min_{y\le x}F_c(y)$。$F_c$ が凸だから、$G_c$ は「左側はそのまま、右側は平ら」になる——これをヒープ表現で表すとどうなるか考える。
ヒント3（誘導）
# 子ごとに Lc を（大きい方へ）マージして Lv に統合、Rc は捨てる
# Lv, Rv に t_v を1個ずつ push
# while Lv.top() > Rv.top():
# lp = Lv から pop, rp = Rv から pop
# cost += lp - rp
# lp を Rv に、rp を Lv に push （入れ替え）模範解答 (Python)
import sys, heapq
def solve():
data = sys.stdin.read().split()
idx = 0
n = int(data[idx]); idx += 1
parent = [-1] * n
for v in range(1, n):
parent[v] = int(data[idx]); idx += 1
t = [int(data[idx + i]) for i in range(n)]; idx += n
children = [[] for _ in range(n)]
root = 0
for v in range(n):
if parent[v] == -1:
root = v
else:
children[parent[v]].append(v)
order, stack = [], [root]
while stack:
v = stack.pop()
order.append(v)
stack.extend(children[v])
post = order[::-1]
L = [None] * n
R = [None] * n
cost = [0] * n
for v in post:
Lv, Rv = [], []
total = 0
for c in children[v]:
lc = L[c]
total += cost[c]
if len(lc) > len(Lv):
Lv, lc = lc, Lv
for val in lc:
heapq.heappush(Lv, val)
heapq.heappush(Lv, -t[v])
heapq.heappush(Rv, t[v])
while Lv and Rv and -Lv[0] > Rv[0]:
lp = -heapq.heappop(Lv)
rp = heapq.heappop(Rv)
total += lp - rp
heapq.heappush(Rv, lp)
heapq.heappush(Lv, -rp)
L[v], R[v], cost[v] = Lv, Rv, total
print(cost[root])
solve()Step-by-Step 解説
1部分木固定コスト関数 $F_v(x)$ の凸性
$F_v(x)=|x-t_v|+\sum_c G_c(x)$ は凸の和で凸。左ヒープ（最大値以下側の折れ点）・右ヒープ（最小値以上側の折れ点）の2本で完全に復元できる。
$F_v(x)=|x-t_v|+\sum_c G_c(x)$ は凸の和で凸。左ヒープ（最大値以下側の折れ点）・右ヒープ（最小値以上側の折れ点）の2本で完全に復元できる。
2$G_c(x)=\min_{y\le x}F_c(y)$ の導出
$F_c$ は $y<L_{c,\mathrm{top}}$ で単調減少、$[L_{c,\mathrm{top}},R_{c,\mathrm{top}}]$ で最小、$y>R_{c,\mathrm{top}}$ で単調増加。よって $G_c$ は「$L_c$ はそのまま、$R_c$ は丸ごと消えて平ら」になる。
$F_c$ は $y<L_{c,\mathrm{top}}$ で単調減少、$[L_{c,\mathrm{top}},R_{c,\mathrm{top}}]$ で最小、$y>R_{c,\mathrm{top}}$ で単調増加。よって $G_c$ は「$L_c$ はそのまま、$R_c$ は丸ごと消えて平ら」になる。
3複数の子のマージと入れ替え補正
複数の子の $L_c$ を合わせ、自分の $t_v$ を両ヒープに push。$L_v$ の最大値が $R_v$ の最小値を超えていれば凸関数として不整合なので、pop→差をコストに加算→入れ替えてpushで回復する（直線版Day103と同じ発想）。
複数の子の $L_c$ を合わせ、自分の $t_v$ を両ヒープに push。$L_v$ の最大値が $R_v$ の最小値を超えていれば凸関数として不整合なので、pop→差をコストに加算→入れ替えてpushで回復する（直線版Day103と同じ発想）。
4実測（本ページ作成時にPythonで実行）
| テスト内容 | 結果 |
|---|---|
| 入力例1（鎖） | 模範解答 14 / 厳密DP 14 一致 |
| 入力例2（分岐木） | 模範解答 6 / 厳密DP 6 一致 |
| ランダム400件（N≤9） | 候補値×木DP $O(N^3)$ との不一致 0件 |
| N=20000のランダム木 | 0.020秒 |
迷った他案と採らなかった理由
| 案 | 採否 | 理由 |
|---|---|---|
| leftist heap / pairing heap を自作しO(log N)一発mergeを実現 | 不採用 | 正しさの検証コストが高く、バグ混入リスクの割に本問の規模（N≤2×10^4）では恩恵が薄い |
Pythonのheapqによるsmall-to-large union（本ページ採用） | 採用 | DSU small-to-largeと同じ償却解析でO(N log N)が保証され、実装・検証が容易 |
| 子の $R_c$ も何らかの形で持ち越す | 不採用 | $G_c(x)=\min_{y\le x}F_c(y)$ の導出上、$R_c$ は数学的に完全に消える。持ち越すと誤り |
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 子の $R_c$ もマージしてしまう | 直線DPの感覚のまま木に持ち込む | 子の $R_c$ は必ず捨てる |
| 大きい方を小さい方へマージ | small-to-largeの向きを逆に | 要素数の少ない方を多い方へpush |
交換ループでcostに符号を逆にして加算 | $L$最大ヒープと$R$最小ヒープの向きの取り違え | 常に lp - rp（$lp>rp$）を加える |
| 制約の向き（親≥子/親≤子）を取り違える | 直線版との類推で符号を逆にしやすい | 逆向きにしたいなら $t_v\to-t_v$ とする |
次のステップ
- 発展: 最終的な割り当て $a_v$ を復元する（ヒープの最終状態から逆算）
- 発展2: 制約を「$a_v\le a_{\mathrm{par}(v)}+k$」のように許容誤差付きに一般化
- 扱わなかった範囲: leftist heapによる真の$O(\log N)$mergeの自前実装
- 次回予告: mergeable heapの速度比較