14267번: 회사 문화 1

문제링크: 14267번: 회사 문화 1

문제

영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하의 모든 부하들이 칭찬을 받는다.

모든 칭찬에는 칭찬의 정도를 의미하는 수치가 있는데, 이 수치 또한 부하들에게 똑같이 칭찬 받는다.

직속 상사와 직속 부하관계에 대해 주어지고, 칭찬에 대한 정보가 주어질 때, 각자 얼마의 칭찬을 받았는지 출력하시오,

입력

첫째 줄에는 회사의 직원 수 n명, 최초의 칭찬의 횟수 m이 주어진다. 직원은 1번부터 n번까지 번호가 매겨져 있다. (2 ≤ n, m ≤ 100,000)

둘째 줄에는 직원 n명의 직속 상사의 번호가 주어진다. 직속 상사의 번호는 자신의 번호보다 작으며, 최종적으로 1번이 사장이다. 1번의 경우, 상사가 없으므로 -1이 입력된다.

다음 m줄에는 직속 상사로부터 칭찬을 받은 직원 번호 i, 칭찬의 수치 w가 주어진다. (2 ≤ i ≤ n, 1 ≤ w ≤ 1,000)

사장은 상사가 없으므로 칭찬을 받지 않는다.

출력

1번부터 n번의 직원까지 칭찬을 받은 정도를 출력하시오.

설명

부하관계를 하나의 트리형태로 나타낼 수 있고 입력에서 부모의 노드번호를 알려주기 때문에 사장인 1번 노드에서 그래프 탐색을 한번 실행해주면된다.

부모노드에서 자식노드로 갈때 자식노드의 칭찬수치에 부모노드의 칭찬수치를 더해주면 쉽게 풀리는 문제이다.

코드

#include <iostream>
#include <vector>
#include <queue>
#define endl '\n'

using namespace std;

int N, M;
vector<int> degree;
vector<vector<int>> child;

void solve() {
	cin >> N >> M;
	child.resize(N);
	degree.resize(N, 0);
	for (int i = 0; i < N; ++i) {
		int t;
		cin >> t;
		if (t == -1) continue;
		child[t - 1].push_back(i);
	}

	while (M--) {
		int a, b;
		cin >> a >> b;
		degree[a - 1] += b;
	}

	queue<int> q;
	q.push(0);
	while (!q.empty()) {
		int now = q.front();
		q.pop();

		for (int c : child[now]) {
			degree[c] += degree[now];
			q.push(c);
		}
	}

	for (int c : degree) {
		cout << c << ' ';
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL); cout.tie(NULL);
	//freopen("input.txt", "r", stdin);
	solve();
	return 0;
}