[백준 33582번] 건물 폭파

 

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

 

제2회 디미고 대회에서 내가 출제한 문제이기도 하고, 에디토리얼에 엄밀한 증명을 적어두지 못해서 여기에 해설을 적어보려고 한다.

 

 

 

처음에는 에디토리얼과 똑같이 일자 트리로 접근해 볼 것이다.

 

모든 $i$ $(1 \leq i \leq N-1)$에 대하여 $i$번 정점과 $i+1$번 정점이 연결되어 있는 일자 트리에서 모든 정점(건물)의 내구도를 0 이하로 만들기 위해서는 $l$번 정점과 $r$번 정점에 각각 $L$, $R$의 폭발을 일으키면 된다고 하자.

 

예를 들어 $N=10$이고 $l=3, r=7, L=3, R=4$일 때가 최적해라고 가정해 보겠다.

그러면 아래와 같이 그림으로 나타낼 수 있다.

각 정점에 닿은 폭발 강도의 총합을 그림으로 나타내보면

이렇게 된다.

 

즉, 모든 $i$ $(1 \leq i \leq N)$에 대하여 $i$번 정점에 전해지는 폭발의 강도는 $\max(L − |l − i|, 0) + \max(R − |r − i|, 0)$이다.

 

이번에는 $m$번 정점에 강도 $L+R$의 폭발을 일으키는 상황으로 가정해 보자.

 

$m$을 $4 \leq m \leq 7$ 범위 내의 어디로 설정해도 폭발 강도의 총합이 이전의 경우를 훨씬 뛰어넘는다.

 

위의 경우, 모든 $i$ $(1 \leq i \leq N)$에 대하여 $i$번 정점에 전해지는 폭발의 강도는 $L + R − |m − i|$가 되는데, $\max(L − |l − i|, 0) + \max(R − |r − i|, 0) \leq L + R − |m − i|$가 성립하는 $m$을 $l \leq m \leq r$ 범위 안에서 무조건 찾을 수 있음이 보장된다는 것을 알 수 있다.

 

즉, 폭발을 일으키는 정점의 개수를 줄이는 것이 절대 손해가 아니므로, 하나의 정점에서 한 번의 폭발을 일으키는 것이 곧 최적해라는 사실을 파악할 수 있다.

 

이제 이를 일반적인 형태의 트리로 확장시켜 볼 것이다.

 

지금까지 설명한 대로 일자 트리 위에서 최적의 $m$ 위치를 구했다고 하자.

 

이제 이 일자 트리(검정)에 정점(하양)을 여러 개 연결하여 일반적인 형태의 트리로 확장시켰다.

일자 트리의 $i$ $(1 \leq i \leq N)$번 정점에 전해진 폭발 강도의 총합을 $B_i$라고 하면, 최적해(한 정점에서 한 번 폭발을 일으키는 경우)일 때 $B_1, B_2, \cdots, B_N$이 최댓값이 된다.

 

$B_i$와 연결된 하얀색 정점에는 $B_i-($$i$번 정점까지의 거리$)$만큼의 폭발이 전해지므로 $B_1, B_2, \cdots, B_N$이 최대인 상태가 하얀색 정점에 전해지는 폭발의 강도 또한 최대인 상태이다.

 

따라서 일반적인 형태의 트리로 확장하여도 최적해를 구하는 방법은 동일하다는 것을 알 수 있다.

 

 

 

한 정점에서 한번 폭발을 일으키는 것이 최적이라는 것을 구했으니 이제 최적의 정점 $m$을 찾는 방법을 알아보자.

 

$dp[i]$를 모든 건물을 무너뜨리기 위해 $i$번 정점에 일으켜야할 폭발의 최소 강도로, $d_{i,j}$ 를 $i$번 정점과 $j$번 정점 사이의 간선 개수로 정의하면 $dp[i] = \min(A_1+d_{i,1}, A_2+d_{i,2}, \cdots, A_N+d_{i,N})$이 성립한다.

 

따라서 모든 $i$ $(1 \leq i \leq N)$에 대하여 $dp[i]$의 최솟값이 문제의 정답이다.

 

탐색 시간을 줄이기 위해 전방향 트리 DP(트리 리루팅)를 사용하면 $O(N)$ 시간에 문제를 해결할 수 있다.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector <int> v[100001] = {};
int p[100001] = {}, dp[100001] = {}, f[100001][2] = {};
void set(int num, int be) {
    dp[num] = p[num];

    for (int i = 0; i < v[num].size(); i++) if (v[num][i] != be) {
        set(v[num][i], num);
        dp[num] = max(dp[num], dp[v[num][i]] + 1);
        if (dp[v[num][i]] + 1 >= f[num][0]) {
            f[num][1] = f[num][0];
            f[num][0] = dp[v[num][i]] + 1;
        }
        else if (dp[v[num][i]] + 1 >= f[num][1]) {
            f[num][1] = dp[v[num][i]] + 1;
        }
    }
    return;
}
void dfs(int num, int be, int add) {
    if (add >= f[num][0]) {
        f[num][1] = f[num][0];
        f[num][0] = add;
    }
    else if (add >= f[num][1]) {
        f[num][1] = add;
    }
    dp[num] = max(dp[num], add);
    for (int i = 0; i < v[num].size(); i++) if (v[num][i] != be) {
        int plus;
        if (f[num][0] == dp[v[num][i]] + 1) plus = f[num][1];
        else plus = f[num][0];

        dfs(v[num][i], num, max(p[num] + 1, plus + 1));
    }
    return;
}
int main() {
    int n;

    cin >> n;
    for (int i = 1; i < n; i++) {
        int a, b;

        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for (int i = 1; i <= n; i++) cin >> p[i];
    set(1, 0);
    dfs(1, 0, 0);
    int ans = 1e9 * 2;
    for (int i = 1; i <= n; i++) ans = min(ans, dp[i]);
    cout << ans;
}