問題概要
$N$頂点の有向木が与えられる. この木の各頂点に対して石を置く, もしくは除くという操作を考える.
ある頂点に石を置きたいときは, その頂点の全ての子に石が置いてある必要がある.
今, 根に石を置きたい. これを達成する操作列の中で, 操作過程の盤面のスコアの最大値が最小であるものを考え, そのスコアを求めなさい.
但しスコアは, 石が置いてある全頂点について, その頂点の重み$w_i$の和を取ったものとして求められる.
制約
- $1 \leq N \leq 10^3$
- $w$は非減少列である
- 全ての頂点はたかだか 2 つの子しか持たない
考察
$\mathrm{dp}[i] := $頂点$i$に石を置くときのスコアの最小値
と定義して逐次的に求められそうなので木 DP を考えます.
遷移
子を何個持つかで場合分けします.
子が 0 個のとき
子が無いので自明に$w[i]$です.
子が 1 個のとき
以下 2 つのうち最大のものです.
- 子に石を置くとき : $\mathrm{dp}[child]$
- 頂点$i$に石を置くとき : $w[i] + w[child]$
子が 2 個のとき
以下 4 つのうち最大のものです.
- 左の子に石を置くとき : $\mathrm{dp}[child1]$
- 右の子に石を置くとき : $\mathrm{dp}[child2]$
- 順番に子に置いていくとき : $\mathrm{min}(w[child1] + \mathrm{dp}[child2], w[child2] + \mathrm{dp}[child1])$
- 頂点$i$に石を置くとき : $w[i] + w[child1] + w[child2]$
反省
子が 2 個のとき, 上の 2 つは必ず 3 個目よりも小さいから無視していいねって勘違いしてた.
提出コード(C++🔆)
木 DP はメモ化再帰で簡単に実装できます.
struct StonesOnATree {
int n;
vector<int> p, w, dp;
vector<vector<int>> graph;
int rec(int cur) {
if (dp[cur] != -1) return dp[cur];
int child = graph[cur].size();
if (child == 0) return dp[cur] = w[cur];
if (child == 1) {
return dp[cur] = max(w[cur] + w[graph[cur][0]], rec(graph[cur][0]));
}
int l = graph[cur][0], r = graph[cur][1];
int ret = w[cur] + w[l] + w[r];
chmax(ret, rec(l));
chmax(ret, rec(r));
chmax(ret, min(w[l] + rec(r), w[r] + rec(l)));
return dp[cur] = ret;
}
int minStones(vector<int> _p, vector<int> _w) {
p = _p, w = _w;
n = w.size();
dp.assign(n, -1);
graph.assign(n, vector<int>());
REP(i, n - 1) graph[p[i]].emplace_back(i + 1);
return rec(0);
}
};