[백준 14267] 회사 문화 1 (C++)

이 문제에서 사원들이 상사와 부하 관계를 맺고 있으므로 계층적 자료구조로 표현이 가능해보인다. 따라서, 트리로 사원들의 관계를 표현할 수 있을 것이다.

❗️ 하지만, 트리의 차수가 지정되지 않았기 때문에, 자식들은 벡터나 리스트에 저장해놓아야 한다.
문제 상황에서는 내리 칭찬을 하기 때문에, 계속 자식으로 내려가기만 하면 된다.

따라서, 부모를 따로 저장해 둘 필요는 없어보인다.

현재까지의 내용을 요약해보면, 자식 노드들은 vector<int> c[100'001]에 저장하면 되고, 부모는 저장할 필요가 없다.

이제, 칭찬에 대한 정보가 주어질 때, 각 직원들이 칭찬을 받은 정도를 구하는 방법을 고민해보자.

먼저, 매 칭찬마다 트리를 탐색해 칭찬 정도를 더해주는 것을 고려해보자. 이는, 시간 복잡도가 $O(M(V + E))$인데, $M \le 10^5$이고, 노드의 갯수 $V$는 $10^5$이하이므로 시간 초과가 발생한다.

따라서, 매번 트리를 탐색하는 방법은 불가능하다.

문제에서 칭찬을 하향식으로 진행한다고 했다.
따라서, 칭찬을 받은 직원을 기록해두고, 트리의 루트인 $1$부터 차례로 방문해가며, 부모노드에서의 칭찬 정도 p[parent]를 자식노드에서의 칭찬 정도 p[child]에 누적해 더해주면 된다. 즉, p[child] += p[parent]가 된다는 의미이다.

트리의 탐색은 재귀적 DFS가 간편하게 구현되므로 이를 토대로 코드를 작성해보자.

#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<int> c[100'001];
int p[100'001];

void dfs(int cur) {
	for (int nxt : c[cur]) {
		p[nxt] += p[cur]; // 부모의 칭찬 정도를 자식의 칭찬 정도에 누적합
		dfs(nxt);
	}
}

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

	cin >> n >> m;
	for (int i = 1, t; i <= n; i++) {
		cin >> t;
		if (t == -1) continue;
		c[t].push_back(i);
	}

	while (m--) {
		int e, w;
		cin >> e >> w;
		p[e] += w;
	}
	dfs(1);
	for (int i = 1; i <= n; i++) cout << p[i] << " ";
}