BOJ 13005 : 행복한 나무

• 문제 링크 : boj.kr/13005
• 난이도 : P4
• 태그 : 트리, DFS

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

struct node {
    int idx;
    ll m_dist;
    ll dist;
};

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

    int n;
    cin >> n;
    vector<ll> num(n+1);
    for(int i = 1; i <= n; i++) cin >> num[i];
    vector<vector<pll>> edge(n+1);
    for(int i = 0; i < n-1; i++) {
        int p, c;
        cin >> p >> c;
        edge[p].emplace_back(i+2, c);
    }
    stack<node> _st;
    _st.push({1, 0, 0});
    vector<bool> check(n+1, false);
    while(!_st.empty()) {
        auto curr = _st.top(); _st.pop();
        if(curr.dist - curr.m_dist > num[curr.idx]) {
            check[curr.idx] = true;
        }
        for(auto u : edge[curr.idx]) {
            node next;
            next.idx = u.first;
            next.dist = curr.dist + u.second;
            next.m_dist = min(next.dist, curr.m_dist);
            _st.push(next);
            if(check[curr.idx]) check[next.idx] = true;
        }
    }
    int cnt = 0;
    for(int i = 1; i <= n; i++) {
        if(check[i]) cnt++;
    }
    cout << cnt;

    return 0;
}

---

풀이

행복한 나무가 되기 위해 어떤 노드를 제거해야 하는지 알아야 한다.

제거해야 할 조건은 다음과 같다.

1. 어떤 노드를 루트까지 이었을 때, 어떤 노드를 시작점으로 하고 경로에 있는 노드를 도착점으로 하는 임의의 dist가 어떤 노드에 적힌 수보다 크다.

2. 경로에 있는 노드 중에 제거해야 하는 노드가 있다.

1번 조건은 임의의 dist 중 최댓값만 확인해도 알 수 있다. 루트부터 경로에 존재하는 모든 노드로 가능 경로의 길이 중 최소값을 루트부터 해당 노드까지의 경로의 길이에서 빼주면 dist의 최댓값을 구할 수 있다.

전체 과정을 DFS를 통해 순회하면 제거해야 할 노드를 구할 수 있다.