BOJ2275: 트리의 높이 줄이기

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

  • 며칠을 붙잡았던 문제, 그냥 피곤해서 풀기 싫었을지도.
  • 두번 탐색하는 형태로 풀었는데 그냥 한번 탐색으로 가능할지도.
  • 각 Edge마다 자녀 Node의 높이를 구한다.
  • H보다 “edge의 cost + 자녀 Node의 높이”가 작아지도록 연산해주면 된다.
  • 생각보다 익숙하지 않아서 쉽잖았다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
using namespace std;

struct Edge {
  int v, c;
};

class Tree {
  int N, root, H;
  vector<vector<Edge>> adj;
  vector<int> cost;
  vector<int> height;
public:
  Tree(int n, int h): N(n), H(h), adj(n+1), height(n+1), cost(n+1) {}
  void input();
  int dfsGetH(int u = -1);
  int dfsReduce(int u = -1);
};

void Tree::input() {
  int v, c;
  for(int i = 1; i <= N; i++) {
    scanf("%d%d", &v, &c);
    if(v || c)
      adj[v].push_back({i,c}), cost[i] = c;
    else
      root = i;
  }
}

int Tree::dfsGetH(int u) {
  if (u == -1) u = root;
  for (auto [v, c] : adj[u])
    height[u] = max(height[u], dfsGetH(v) + c);
  return height[u];
}

int Tree::dfsReduce(int u) {
  if (u == -1) u = root;
  int total = cost[u] + height[u];
  int needToReduce = total - H;
  if (needToReduce <= 0) return 0;
  if (needToReduce <= cost[u]) return needToReduce;
  int ans = cost[u];
  for (auto [v, c] : adj[u])
    ans += dfsReduce(v);
  return ans;
}

int main() {
  int N, H;
  scanf("%d%d", &N, &H);
  Tree tree(N, H);
  tree.input();
  tree.dfsGetH();
  cout << tree.dfsReduce();
}