취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2275번 문제인 트리의 높이 줄이기이다.
문제는 아래 링크를 확인하자.

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

루트에 가까운 에지의 길이를 줄이면 그 에지의 아래에 달려있는 각 노드들의 깊이가 모두 감소하므로, greedy한 접근으로 루트에 가까운 노드의 길이부터 필요한만큼씩 줄여나가 문제를 해결하자.

이 과정에서 필요한 각 노드를 루트로 갖는 서브트리의 깊이는 dfs로 미리 전처리해 사용하자.

아래는 제출한 소스코드이다.

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

int N, H;
vector<pair<int, int>> G[10001];
int depth[10001];

int dfs1(int cur) {
	int& dpt = depth[cur];
	for (auto& nxt : G[cur]) {
		dpt = max(dpt, dfs1(nxt.first) + nxt.second);
	}
	return dpt;
}

int dfs2(int cur, int h) {
	int ret = 0;
	for (auto& nxt : G[cur]) {
		int dpt = nxt.second + depth[nxt.first];
		if (dpt <= h) continue;
		int red = dpt - h;
		if (nxt.second >= red) ret += red;
		else ret += dfs2(nxt.first, h) + nxt.second;
	}

	return ret;
}

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

	cin >> N >> H;
	for (int n = 1; n <= N; n++) {
		int x, h; cin >> x >> h;
		G[x].emplace_back(make_pair(n, h));
	}

	dfs1(0);

	cout << dfs2(0, H);
}