회사 문화 1

문제 분석 및 풀이

설계 분석

• 자식들의 정보만 가지는 트리를 구현하고, 중복되는 입력을 한번에 처리하는 문제.
• m개의 간선을 입력하고 루트부터 n개의 노드를 순회하며 자식 노드에 값을 중첩시킨다.
  $O(N+M)$

풀이

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
using namespace std;
const int MAX = 100'001;
int n, m;
int costArr[MAX];
unordered_map<int, vector<int>> g;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

	// 자식 노드를 저장하는 그래프 초기화
    cin >> n >> m;
    for (int val=1; val<=n; val++)
    {
        int parent;
        cin >> parent;
        g[parent].push_back(val);
    }

	// 입력값 기록
    for (int i=0; i<m; i++)
    {
        int target, value;
        cin >> target >> value;
        costArr[target] += value;
    }

	// root노드부터 점점 내려가면서 값을 중첩
    queue<int> q;
    q.push(1);
    while(!q.empty())
    {
    	// 현재 방문한 노드
        int front = q.front(); q.pop();
        // 현재 노드의 인접노드에 값을 누적
        for (auto v : g[front])
        {
            costArr[v] += costArr[front];
            q.push(v);
        }
    }

    for (int i=1; i<=n; i++)
        cout << costArr[i] << " ";


    return 0;
}