問題概要

$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);
    }
};