BOJ)2275 트리의 높이 줄이기

문제: icpc.me/2275

트리에서 모든 리프까지의 거리가 H이하로 되게 만들 때 비용의 최솟값을 구하는 문제이다.

우리는 가능하다면 부모에서 높이를 줄여야지 한번에 여러 리프들의 높이를 동시에 줄이는게 가능하다는 사실을 이용하여

모든 리프에 줄여야할 가중치를 할당하고 바텀업 방식으로 부모에서 높이를 줄이는게 가능하다면 줄이는 방식으로 문제를 해결해주면 된다.

문제를 해결하기 위하여 dfs로 전처리를 해줘야하는데 해당 노드의 깊이 중첩 가중치를 미리 구해주면 쉽게 계산해 줄 수 있다.

아래 코드에서 각 배열이 의미하는건 r[v]는 v노드에서 줄여야하는 가중치이고 d[v]는 v까지의 누적 가중치이다.

 

#include <cstdio>
#include <algorithm>
#include <vector>
#define MAX_N 10000
using namespace std;
int n, h, r[MAX_N + 1], visited[MAX_N + 1], d[MAX_N + 1], par[MAX_N + 1], root, x, y, ans;
vector<vector<pair<int, int>>> vt;
vector<vector<int>> dph;
void dfs(int v, int dh, int dis) {
    visited[v] = true;
    d[v] = dis;
    dph[dh].push_back(v);
    if (!vt[v].size())
        r[v] = dis - h;
    for (auto next : vt[v]) {
        if (visited[next.first])
            continue;
        dfs(next.first, dh + 1, dis + next.second);
    }
}
int main() {
    scanf("%d%d", &n, &h);
    vt.resize(n + 1);
    dph.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &x, &y);
        if (x == 0)root = i;
        else {
            par[i] = x;
            vt[x].push_back({ i,y });
        }
    }
    dfs(root, 0, 0);
    for (int i = dph.size() - 1; i >= 0; i--) {
        for (auto v : dph[i]) {
            if (d[par[v]] >= r[v]) {
                r[par[v]] = max(r[v], r[par[v]]);
            }
            else {
                r[par[v]] = d[par[v]];
                ans += r[v] - d[par[v]];
            }
        }
    }
    printf("%d", ans);
    return 0;
}