백준 25091, Chain Reactions

개요

문제 링크
골드 1, Greedy, DP, Tree
리프노드부터 아직 방문하지 않은 부모를 방문하며 구한 구간의 최댓값의 합의 최댓값

---

접근

1. 요즘 코포가 완전히 박살이 나서 코포식 운영을 해보려고 한다. 쓰잘데기 없는 기하학 문제는 그만풀고 구글 코드잼같은 메이저 대회의 문제들을 풀면서 시간도 재보고 하려고 한다. 문제는 코포 연습하기 진짜 좋은 문제다. 스타일이 똑같다.

2. 문제로 돌아오면, 참 괴상한 문제인데 핵심은 자신이 어떤 리프에 의해 init되느냐 하는 것이다. 2번 예시를 약간 변형해서 보자.

   1. 그림을 그려보면 이렇게 되는데, 각각 무엇을 통해 init이 되는 것이 최선인지 확인을 해보자.

      

      우선 위 예시의 정답은 4,3,5,6 순으로 init하는 것이므로 210이 된다.

   2. 먼저 2를 보자. 2은 4에 의해, 3,5는 스스로 init이 된다. 그럼 이때 2,3,4,5의 트리를 구성하는 과정에서 최대의 이득은 90점이 된다.

      

      문제는 이때 init에서 얻은 이득과 나머지 자식의 이득의 총합을 구분해 생각해야 한다는 것이다.
      왜냐? 어차피 init은 최솟값을 통해서만 하는 것이 이득이다. 그럼 나머지 자식들이 init을 하는 과정에서 얻는 이득은 자신의 부모의 init과 관련이 없지만, 자신이 init을 하는 과정에서 얻는 이득은 부모의 init과 관련이 있다. 말이 엄청 헷갈리는데 아래에서 1번의 init을 통해 이해해보자.

   3. 1이 init되기 위한 최선의 경로를 보면 4→3→1을 거치면서 해주는 것이 이득이다. 그럼 아래와 같이 그림이 나타내진다.

      

      만약 2를 init하는 과정에서의 이득을 구분하지 않고 2에 90을 때려넣었다면? 6을 구성하는 이득이 더 작으므로 1은 init을 위해 6을 선택하게 된다. 이때의 답은 init에 100, child가 90이라 190이 된다. 하지만 4를 선택하는 것이 이득이고 답은 210이 나와야 한다.

3. 자 여기까지 봤으면 DFS를 이용해 쉽게 구현할 수 있다. 자식들 중 init에 최소 이익이 든 자식을 구하고, 그 자식의 이익과 자신의 이익 중 최댓값을 자신의 init 이익으로 업데이트 한다. 그리고 자식의 자식들의 이익은 전부 더해준다.

코포로 치면 Div2 D는 될 것 같은데 2시간은 걸린 것 같다. 진짜 물다이아가 확실하다.

---

Pseudo code

DFS(node) {
    if (leaf(node)) {
        // 만약 리프라면 자신이 자신을 init
        return {Funny, 0}
    }
    init, children
    for (child:adj[node]) {
        auto [initChild, initGrandChild] = DFS(child)
        // 자식 중 최소 init을 가진 자식 찾기
        init = min(init, initChild)
        // 자식들의 init과 손자의 init 일단 다 더해두기
        children += initChild + initGrandChild
    }
    // 최소로 선택된 자식의 init은 빼줘야 함
    children -= init
    // 만약 자신의 Funny가 더 크다면 Funny로 업데이트
    init = max(init, Funny)
    return {init, children}
}

answer = DFS(0)

---

Source code

#include <bits/stdc++.h>
using namespace std;

using ld = long long;
using vec = vector<ld>;
using snt = set<int>;
using mat = vector<snt>;
using pii = pair<ld, ld>;

pii DFS(mat &adj, vec &F, int n) {
    if (!adj[n].size()) return {F[n], 0};
    ld self = 2e15, res = 0;
    for (auto &x : adj[n]) {
        auto [v, r] = DFS(adj, F, x);
        self = min(self, v);
        res += v + r;
    }
    res -= self;
    self = max(self, F[n]);
    return {self, res};
}

void test() {
    int n;
    cin >> n;
    mat adj(n + 1);
    vec F(n + 1, 0);
    for (int i = 1; i <= n; i++)
        cin >> F[i];
    for (int p = 1; p <= n; p++) {
        int x;
        cin >> x;
        adj[x].insert(p);
    }
    auto [a, b] = DFS(adj, F, 0);
    cout << a + b << "\n";
}

int main() {
    cin.tie(0), ios::sync_with_stdio(0);
    int t;
    cin >> t;
    for (int i = 1; i <= t; i++) {
        cout << "Case #" << i << ": ";
        test();
    }
}