[백준] 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번의 직원까지 칭찬을 받은 정도를 출력하시오.

 

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 };
int n, m, lazy[100001],d[100001], r, i, w, x;
vi adj[100001];
void dfs(int k) {
		d[k] += lazy[k];
		for (auto c : adj[k]) {
			lazy[c] += lazy[k];
			dfs(c);
		}
}
int main() {
	FAST;
	cin >> n >> m;
	REP(i, n) {
		cin >> x;
		if(x!=-1)adj[x].push_back(i);
	}
	while (m--) {
		cin >> i >> w;
		lazy[i] += w;
	}
	dfs(1);
	REP(i, n) {
		cout<< d[i] << " ";
	}
}

세그먼트 트리에서 사용하는 기법인 lazy propagation의 전파 방식과 비슷한(?)논리 입니다.

탑바텀방식으로 현재 lazy값이 존재하면 업데이트 후, 자식노드에 전파합니다.