[BOJ] 백준 14267 내리 갈굼

문제 링크

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

1) 각 정점이 내리 갈굼 받는 정도를 저장한다.

2) 1부터 pre-order로 순회하며 부하에게 갈굼을 물려준다.

정답 코드

	#include <iostream>
	#include <vector>
	using namespace std;
	int n, m, lazy[100001];
	vector<vector<int>> p;
	void dfs(int now) {
	for (int next : p[now]) {
	lazy[next] += lazy[now];
	dfs(next);
	}
	}
	int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	p.resize(n + 1);
	int x; cin >> x;
	for (int i = 2; i < n + 1; i++) {
	cin >> x;
	p[x].push_back(i);
	}
	int y;
	for (int i = 0; i < m; i++) {
	cin >> x >> y;
	lazy[x] += y;
	}
	dfs(1);
	for (int i = 1; i < n + 1; i++) {
	cout << lazy[i] << ' ';
	}
	}

view raw 14267.cpp hosted with ❤ by GitHub