Codeforces Round #530 (Div. 2) D. Sum in the tree

문제링크 : https://codeforces.com/contest/1099/problem/D

결론부터 말하자면 틀린 문제이다. 당연하다고 생각하고 여러 가지를 다시 생각해보지 않았기 때문에 제대로 풀지 못했다.

<입력>

- 노드의 개수 (n)

- 2번부터 노드의 parent 노드 번호

- 1번부터 노드의 S_v (해당 노드부터 루트까지 경로상에 있는 모든 노드의 value 합)

  [ 단, 루트의 height을 1이라고 할 때 height이 짝수인 칸은 -1로 주어짐 ]

<출력>

- 해당 트리에서 모든 노드의 value들의 합 중 최소값 (조건에 맞는 트리가 될 수 없을 경우 -1)

<풀이>

문제의 상황은 height이 짝수인 노드들의 루트까지의 sum을 -1로 바꿔버린 상황이다.

즉, height이 홀수인 칸은 맞는 sum들이 들어온다.

따라서 항상 부모의 sum보다 커야하고 만족하지 못할 경우 조건에 맞는 트리가 될 수 없다.

루트를 제외한 모든 노드의 value는 부모의 sum에서 자신의 sum을 뺀 값이다.

height이 홀수인 칸은 sum이 정상적으로 들어오기 때문에 height이 짝수인 칸의 sum을 어떻게 정해줄 것이냐가 문제를 해결하는 방법이다.

나는 당연히 모든 노드의 value 합을 최소로 만들어줘야 하기 때문에 height이 짝수인 칸의 value를 모두 0으로 만들어줬다.

쉽게 예를 들어보면,

위와 같은 입력이 주어진다고 생각해보자. 2, 3번 노드에는 sum이 -1이 들어왔다. 그러므로 모두 0을 넣고 sum은 1이 된다.

다음으로 4, 5, 6번 노드의 경우 2번노드의 sum이 1므로 각각 2, 3, 4가 들어간다.

이 과정을 모두 거치고 아래와 같은 그림이 만들어진다.

모든 노드의 value를 합치게 되면 1 + 0 + 0 + 2 + 3 + 4 = 10이 된다.

이와 같이 0으로 만드는 것이 당연히 최소일 것이라고 생각했다.

하지만 이 것은 1차원적인 생각이었고 큰 실수였다.

내가 간과한 점은 height이 짝수인 노드들이 그 자식들에게 영향을 끼친다는 점이었다.

자식이 없거나 1개인 경우는 0을 넣어줘도 문제가 없다. 하지만, 위 그림과 같이 자식이 3개인 경우

위 그림과 같이 2번 노드의 value를 2로 만들어준다면 1 + 2 + 0 + 0 + 1 + 2 = 6이 된다.

처음 생각했던 경우보다 더 최소의 결과를 만들어낸 것이다.

따라서, 짝수층의 sum은 인접해있는 모든 자식들의 sum 중 최소값이 들어가야 한다.

짝수층의 노드 자신만 최소가 되는 것(실수한 경우)보다 인접한 자식 모두를 최소로 만드는 것(올바른 경우)이 전체를 최소로 만드는 방법인 것이다.

단편적인 부분만 보지 말고 전체를 보려고 노력하자.

---

- 소스 코드 -

(코포 종료 후 다시 제출해서 정답임을 확인한 코드)

#include<iostream>
#include<vector>
 
using namespace std;
 
typedef long long ll;
 
struct node {
    int parent;
    int value;
    int sum;
    int depth;
    vector<int> son;
 
    node() {
        parent = 0;
        value = 0;
        sum = -1;
        depth = 0;
    }
};
 
node nodes[100002];
 
int main(void) {
    nodes[1].depth = 1;
    int num;
    cin >> num;
    for (int i = 2; i <= num; i++) {
        scanf("%d", &nodes[i].parent);
        nodes[i].depth = nodes[nodes[i].parent].depth + 1;
        nodes[nodes[i].parent].son.push_back(i);
    }
    
    ll result = 0;
    bool flag = true;
    for (int i = 1; i <= num; i++) {
        scanf("%d", &nodes[i].sum);
    }
    nodes[1].value = nodes[1].sum;
    
 
    for (int i = 2; i <= num; i++) {
        if (nodes[nodes[i].parent].sum!=-1) {
            if (nodes[i].depth % 2 == 1) {
                if (nodes[i].sum < nodes[nodes[i].parent].sum) {
                    flag = false;
                }
                else if (nodes[i].sum >= nodes[nodes[i].parent].sum) {
                    nodes[i].value = nodes[i].sum - nodes[nodes[i].parent].sum;
                }
            }
            else {
                int min = INT_MAX;
                for (int j = 0; j < nodes[i].son.size(); j++) {
                    if (min > nodes[nodes[i].son[j]].sum) {
                            min = nodes[nodes[i].son[j]].sum;
                    }
                }
                if (min == INT_MAX) {
                    nodes[i].sum = nodes[nodes[i].parent].sum;
                }
                else {
                    nodes[i].sum = min;
                }
                nodes[i].value = nodes[i].sum - nodes[nodes[i].parent].sum;
                if (nodes[i].value < 0) {
                    flag = false;
                }
            }
        }
        else {
            flag = false;
        }
    }
    if (flag) {
        for (int i = 1; i <= num; i++) {
            result += nodes[i].value;
        }
        cout << result << endl;
    }
    else {
        cout << "-1" << endl;
    }
}

---