Boj 14267 c++ 회사문화

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

 

1번에서 N번까지의 회사원들에 대한 직속 상사에 대한 정보가 주어진다.

1번 직원은 사장이므로 직속 상사가 없다.

다음 M 개의 줄에는 각 직원들이 받은 칭찬의 지수가 주어진다.

칭찬은 직속 부하 직원에게 차례대로 전파된다.

 

칭찬의 지수가 모두 주어졌을 때 각 직원이 받은 칭찬의 총량을 구해야 하는 문제이다.

알고리즘 태그를 보고 들어온 문제이기에 트리 dp 라는 것을 알았다.

루트 노드에 대한 정보를 바탕으로 트리를 만들고, 자식노드에 대한 정보를 저장한다.

 

이때 인접 노드 중에서 부모 노드가 아닌 것만을 자식노드 리스트에 추가해주면 된다.

 

칭찬의 합을 구하는 법도 비슷하다. 루트 노드에서 시작하여 자신이 받은 칭찬을 모두 자식 노드에게 더해주면 된다.

더이상 자식노드가 없는 리프 노드에 도달하였을 때 끝나게 된다.

 

이렇게 재귀적으로 각 직원별 칭찬의 총량을 구할 수 있다.

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> connected(100001);
vector<vector<int>> child(100001);
int dp[100001];

void mt(int curr, int parent) {
    for(auto c : connected[curr]) {
        if(c != parent) {
            child[curr].push_back(c);
            mt(c, curr);
        }
    }

}

void sum(int curr) {
    for(auto c : child[curr]) {
        dp[c] += dp[curr];
        sum(c);
    }
}
int main() {
    cin.tie(NULL);
    cout.tie(NULL);

    int N, M;

    cin >> N >> M;
    
     for(int i = 1; i <= N; i++) {
        int j;
        cin >> j;
        if(j < 0)
            continue;
        connected[i].push_back(j);
        connected[j].push_back(i);
    }

    for(int i = 0; i < M; i++) {
        int W, V;
        cin >> W >> V;
        dp[W] += V;
    }

    mt(1, -1);
    sum(1);

    for(int i = 1; i <= N; i++) {
        cout << dp[i] << " ";
    }
}