CPSCO2019 Session2 E - Mogu Mogu Gummi

E - Mogu Mogu Gummi

問題

頂点 $0$ を根とする $n$ 頂点の根付き木が与えられる．頂点 $v$ は頂点 $p_v (\lt v)$ と耐久力 $h_v$ の辺で結ばれている．

この木に対して，以下の操作を好きな回数だけ行う．

$0$ 以外で $0$ と連結な頂点 $v$ を 1 つ選ぶ．
$0$ と $v$ を結ぶパス上の辺の耐久力を $1$ 減らす．
耐久力が $0$ になった辺は削除される．

最終的な連結成分数の最大値を求めよ．

制約

$2 \leq n \leq 5 \times 10^3$
$1 \leq h_i \leq 10^9$

考察

$dp_{v, k} =$ 「 $v$ を根とする部分木を $k$ 個の連結成分に分解するとき， $v$ から上に伸びる辺にかかるダメージの最小値」という DP を考える．これは $v$ の各子 $u$ に対して再帰的に $dp_u$ を求めて， $v$ と $u$ を切るかどうかの処理をして，それらを左からマージしていくことで求められる．

気になるのは計算量だが，実はこれが $\Theta(n^2)$ になるというのが俗に言う「木の二乗 DP」である．これを簡単に示す．

計算量の証明

$v$ の子をそれぞれ $u_1, \cdots, u_k$ として， $u_i$ を根とする部分木のサイズを $s_i$ とする．また頂点 $v$ を根とする部分木のサイズを $n$ とする．

長さ $s, t$ の DP 配列のマージに時間 $2st$ かかるとき¹，左から順にマージしていくと全体の計算量は

$$ 2 s_1 s_2 + 2 (s_1 + s_2) s_3 + \cdots + 2 (s_1 + \cdots + s_{k - 1}) s_k = 2 \sum_{i \lt j} s_i s_j = \left( \sum_{i} s_i \right)^2 - \sum_{i} {s_i}^2 $$

となる．そして $u_i$ を根とする部分木に対して DP 配列を求めるのに ${s_i}^2$ 時間かかるとすると，右辺の第 2 項が消えて $\left( \sum_{i} s_i \right)^2 = n^2$ が残る． $\square$

係数の $2$ は後々計算が楽なのでつけてあるだけ． ↩︎

実装例

提出 #8231839 - CPSCO2019 Session2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72


#include <iostream>
#include <vector>
#include <functional>

template <class Cost = int>
struct Edge {
    int src, dst;
    Cost cost;
    Edge(int src = -1, int dst = -1, Cost cost = 1)
        : src(src), dst(dst), cost(cost){};
};

template <class Cost = int>
using Graph = std::vector<std::vector<Edge<Cost>>>;

using lint = long long;
constexpr lint INF = 1LL << 40;

int main() {
    int n;
    std::cin >> n;

    Graph<lint> graph(n);
    for (int v = 1; v < n; ++v) {
        int p;
        lint h;
        std::cin >> p >> h;
        graph[p].emplace_back(p, v, h);
    }

    std::function<std::vector<lint>(int)> dfs =
        [&](int v) {
            std::vector<lint> cost{0};
            // i個の連結成分を作るとき，上への辺が受ける最小ダメージ

            for (auto e : graph[v]) {
                auto chcost = dfs(e.dst);

                // eを切った場合を加味する
                chcost.push_back(INF);
                for (int num = chcost.size() - 1; num >= 0; --num) {
                    if (chcost[num] > e.cost) {
                        // 部分木を分解する前にeが切れてる
                        chcost[num] = INF;
                    } else {
                        // eを切って1つ増やす
                        chcost[num + 1] = std::min(chcost[num + 1], e.cost);
                    }
                }

                // マージ
                std::vector<lint> ncost(cost.size() + chcost.size() - 1, INF);
                for (int i = 0; i < cost.size(); ++i) {
                    for (int j = 0; j < chcost.size(); ++j) {
                        ncost[i + j] = std::min(ncost[i + j],
                                                cost[i] + chcost[j]);
                    }
                }
                std::swap(cost, ncost);
            }
            return cost;
        };

    auto ans = dfs(0);
    int num;
    for (num = n - 1; num >= 0; --num) {
        if (ans[num] < INF) break;
    }
    // 根の分を加算
    std::cout << num + 1 << std::endl;
    return 0;
}