[백준] 14267 - 내리갈굼

https://www.acmicpc.net/problem/14267

14267번: 내리 갈굼

갈굼 수치를 입력받을 때, 바로 모든 수치를 전파하는 것은 비효율적이다.

모든 수치를 입력받은 후에, 해당 부모의 수치를 갱신하고 자식에게 전파하는 경우 불필요한 탐색과 갱신을 줄일 수 있다.

이 문제의 경우에는 부모가 자식보다 작은 수를 가지므로 1번부터 순서대로 답을 구하면 된다.

 

<C++ 코드>

#include <cstdio>
#include <vector>
using namespace std;
 
int n, m;
vector<int> par[100001];
vector<int> re, diff;
 
int main(){
    int t;
    scanf("%d %d", &n, &m);
    re.resize(n+1);
    diff.resize(n+1);
    scanf("%d", &t);
    for(int i=2; i<=n; i++){
        scanf("%d", &t);
        par[t].push_back(i);
    }
    for(int i=0; i<m; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        diff[a] += b;
    }
    for(int i=1; i<=n; i++){
        if(diff[i] != 0){
            re[i] += diff[i];
            for(int j=0; j<par[i].size(); j++){
                diff[par[i][j]] += diff[i];
            }
            diff[i] = 0;
        }
        printf("%d ", re[i]);
    }
    return 0;
}