[백준] 14267 내리 갈굼

문제를 해석하면 직속 상사에게 혼나면 아래도 다 혼난다

그 때 모두가 혼난 정도를 출력하면 된다

트리로 구성되기 때문에 혼나는 정도를 미리 저장해두고

dfs를 돌리며 자식들에게 값을 물려주면 된다

처음에 순서대로 방문한다고 혼자 착각해서 한번 틀렸다 ㅎㅎ..

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXN = 1e5 + 5;
int n, m;
vector<vector<int>> Graph;
int cost[MAXN];
bool check[MAXN];
int ans[MAXN];
void dfs(int x,int sum) {
    check[x] = true;
    int c = sum + cost[x];
    ans[x] = c;
    for (int i = 0; i < Graph[x].size(); i++) {
        int next = Graph[x][i];
        if (!check[next]) dfs(next, c);
    }
}
int main() {
    scanf(" %d %d", &n, &m);
    Graph.resize(n);
    for (int i = 0; i < n; i++) {
        int x; scanf(" %d", &x);
        if (i == 0) continue;
        x--; 
        Graph[x].push_back(i);
    }
    for (int i = 0; i < m; i++) {
        int a, b; scanf(" %d %d", &a, &b);
        a--; cost[a] += b;
    }
    dfs(0, 0); 
    for (int i = 0; i < n; i++) printf("%d ", ans[i]); puts("");
}