이것 저것 &

문제링크:www.acmicpc.net/problem/14267

dfs 문제였습니다.

이때 완전탐색 횟수를 줄이는게 핵심인 문제였습니다.

우선 첫번째 코드를 먼저 보시죠.

#include <iostream>
#include <vector>
using namespace std;

int n = 0, m = 0;
int cost[100001] = { 0, };
vector <int> vec[100001];
int h, w;

void dfs(int current) {

	cost[current] += w;
	for (int i = 0; i < vec[current].size(); i++) {
		dfs(vec[current][i]);
	}
}

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		int temp;
		cin >> temp;
		if (i == 1) continue;
		vec[temp].push_back(i);
	}

		
	for (int i = 1; i <= m; i++) {
		cin >> h >> w;
		dfs(h);
	}

	for (int i = 1; i <= n; i++) {
		cout << cost[i];
		if (i == n)
			break;
		cout << ' ';
	}
	cout << '\n';

	return 0;
}

일반적으로 생각할 수 있는 방법입니다. 

근데 이렇게 제출하면 당연히 시간 초과가 납니다. 

좀더 효율적으로 탐색할 수 없을까 고민을 하던중에 

dfs를 한번만 돌아도 되는 아이디어를 생각했습니다.

아래처럼 dfs(1)을 호출하고 줄줄이 이전 cost값을 더해주는 형태로 구현했습니다. 

#include <iostream>
#include <vector>
using namespace std;

int n = 0, m = 0;
int cost[100001] = { 0, };
vector <int> vec[100001];
int h, w;

void dfs(int current) {

	for (int i = 0; i < vec[current].size(); i++) {
		cost[vec[current][i]] += cost[current];
		dfs(vec[current][i]);
	}
}

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		int temp;
		cin >> temp;
		if (i == 1) continue;
		vec[temp].push_back(i);
	}

		
	for (int i = 1; i <= m; i++) {
		cin >> h >> w;
		cost[h] += w;
	}
	dfs(1);
	for (int i = 1; i <= n; i++) {
		cout << cost[i];
		if (i == n)
			break;
		cout << ' ';
	}
	cout << '\n';

	return 0;
}