백준17674 특별관광도시

작성일 | In

문제 링크

  • https://icpc.me/17674

문제 출처

  • 2018/2019 JOISC Day3 1번

사용 알고리즘

  • 트리 DP
  • 그리디
  • 센트로이드

시간복잡도

  • $O(N \log^2 N)$

풀이

선택되지 않은 간선의 가중치 합을 최소화하는 문제입니다. 반대로 선택된 간선의 가중치 합을 최대화하는 문제로 생각해서 해결해 봅시다.

Subtask 2. $Q = 1, E_1 = 1$ (7점)

선택한 정점이 트리의 루트라고 생각합시다. 루트로 올라가는 간선의 가중치를 최소화하는 문제입니다.
Tree DP를 이용하면 $O(N)$ 전처리를 통해 각 정점이 루트인 경우에 대한 답을 상수 시간에 구할 수 있습니다. 이 문제에 도전할 정도의 실력이라면 다들 알고 있을 것이라 믿습니다.

코드

Subtask 4. $N \leq 2\,000$ (30점)

루트를 고정하는 Subtask 2의 아이디어는 그대로 가져갑니다. 추가로, 루트 정점과 리프 정점만 선택해도 정답을 찾을 수 있다는 점을 관찰해야 합니다. 리프 정점이 아닌 두 정점을 선택하는 것이 최적이라면, 자식 정점을 대신 선택해도 같거나 더 좋은 답을 낼 수 있다는 점을 생각해 보면 좋습니다.

루트가 고정된 상태에서 정점을 선택하는 것은 세 가지 경우로 나눌 수 있습니다.

  1. 루트만 선택 (정점 1개 선택)
  2. 루트 정점을 선택하고 리프 정점을 1개 이상 선택
  3. 루트 정점을 선택하지 않고 리프 정점을 2개 이상 선택

세 가지 경우 모두 루트로 향하는 간선이 전부 선택된다는 점을 관찰할 수 있습니다. 단, 세 번째 경우에서는 두 개 이상의 서로 다른 서브 트리에서 리프를 선택해야 합니다. 2, 3번 경우에서 어떤 간선들이 추가로 선택되는지 알아봅시다.

두 번째 경우부터 살펴보겠습니다. 두 번째 경우에서는 루트에서 선택한 정점으로 가는 간선이 추가로 선택됩니다. 따라서 이 경우에는 루트가 있는 트리에서 정점 $K$개를 선택했을 때 루트에서 선택한 정점으로 가는 간선들의 가중치 합을 최대화하면 됩니다. 이런 문제는 DP 또는 그리디를 이용해 해결할 수 있습니다.

$D(v, k)$를 $v$를 루트로 하는 서브 트리에서 리프를 $k$개 선택했을 때의 최댓값이라고 정의합시다. DP를 MCMF로 모델링할 수 있기 때문에 $D(v, \ast)$는 볼록합니다. 따라서 $D(u, \ast)$와 $D(v, \ast)$를 $D(r,k_1+k_2) \leftarrow D(u,k_1) + D(v,k_2)$와 같이 합칠 때 기울기가 큰 것부터 하나씩 끼워넣으면 됩니다. 우선순위 큐와 Small to Large를 이용해 $O(N \log^2 N)$에 $D(root, \ast)$를 모두 구할 수 있습니다.

이 DP 풀이를 응용하면 그리디 기법을 이용해 $O(N \log N)$ 시간에 해결할 수도 있습니다. $D(v, k) - D(v, k-1)$은 $k$번째로 정점을 선택했을 때 추가되는 경로를 의미합니다. $D(v, \ast)$에 저장되어 있는 경로 중 $v$보다 위로 확장될 수 있는 경로는 $D(v, 1) - D(v, 0)$ 뿐이고, 다른 나머지 경로들은 $v$ 밑에서 끊어져서 더 이상 연장되지 않습니다.
끊어진 경로들은 굳이 Small to Large에서 주고 받을 필요가 없고, 전역에 선언되어 있는 우선순위 큐 하나에서 모두 관리해도 무방합니다. 즉, $D(v, \ast)$에서 $v$ 밑에 있는 모든 경로를 관리하는 대신 가장 긴 경로 하나만 관리하고, 다른 나머지 경로는 전역에 있는 우선순위 큐에서 관리할 수 있습니다. 이때의 시간 복잡도는 $O(N \log N)$입니다.
한국에서는 KOI 2013 고등부 4번. 수족관 3의 풀이로도 잘 알려져 있습니다.

따라서 두 번째 경우는 $O(N \log N)$ 시간에 처리할 수 있습니다.

이제 세 번째 경우를 살펴보겠습니다. 세 번째 경우에서는 두 개 이상의 서로 다른 서브 트리에서 리프 정점을 선택해야 합니다. 한쪽에서만 정점을 뽑으면, 그 서브 트리에서 루트로 올라가는 간선이 선택되지 않을 수 있기 때문입니다.
사실 세 번째 경우도 두 번째 경우와 비슷하게 처리할 수 있습니다. 각 경로가 어떤 서브 트리에서 유래했는지 함께 저장한 다음, 가장 큰 경로와 다른 서브 트리에서 유래한 가장 큰 경로를 강제로 포함시키면 됩니다. 따라서 세 번째 경우도 $O(N \log N)$ 시간에 처리할 수 있습니다.

루트가 고정되어 있을 때 $O(N \log N)$ 만큼 걸리므로 전체 시간 복잡도는 $O(N^2 \log N)$입니다.

코드

Subtask 6. (100점)

Subtask 4의 풀이에 Centroid Decomposition을 적용하면 $O(N^2 \log N)$을 $O(N \log^2 N)$으로 줄일 수 있습니다.
Subtask 4 코드에 센트로이드 관련 처리 부분만 추가하면 됩니다.

전체 코드

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll N, Q, Sum, C1, C[202020], R[202020];
vector<pair<ll,ll>> G[202020];
int S[202020], U[202020];

int GetSize(int v, int b=-1){
    S[v] = 1;
    for(auto [i,w] : G[v]) if(i != b && !U[i]) S[v] += GetSize(i, v);
    return S[v];
}

int GetCent(int v, int n, int b=-1){
    for(auto [i,w] : G[v]) if(i != b && !U[i] && S[i]*2 > n) return GetCent(i, n, v);
    return v;
}

void TreeDP(int v, int b=-1, ll up=0, ll dw=0){
    for(auto [i,w] : G[v]) if(i == b) C1 += w, up += w;
    C[v] = dw - up;
    for(auto [i,w] : G[v]) if(i != b) TreeDP(i, v, up, dw+w);
}

ll CostToRoot(int root){
    return C1 + C[root];
}

vector<pair<ll,ll>> PathsFromRoot(int root){
    vector<pair<ll,ll>> paths;
    function<ll(int,int,int)> dfs = [&](int st, int v, int b) -> ll {
        ll mx = 0;
        for(auto [i,w] : G[v]){
            if(i == b || U[i]) continue;
            ll nxt = dfs(st, i, v) + w;
            if(nxt > mx) swap(mx, nxt);
            if(mx != 0) paths.emplace_back(nxt, st);
        }
        return mx;
    };
    for(auto [i,w] : G[root]) if(!U[i]) paths.emplace_back(dfs(i, i, root) + w, i);
    return paths;
}

void Go(int root){
    root = GetCent(root, GetSize(root)); U[root] = 1;

    ll to_root = CostToRoot(root);
    vector<pair<ll,ll>> paths = PathsFromRoot(root);
    sort(paths.begin(), paths.end(), greater<>());

    // case 1. only root
    R[1] = max(R[1], to_root);
    if(paths.empty()) return;

    // case 2. root and some leaves
    ll cost2 = to_root + paths[0].first;
    R[2] = max(R[2], cost2);
    for(int i=1; i<paths.size(); i++) R[i+2] = max(R[i+2], cost2 += paths[i].first);

    // case 3. only leaves
    int idx = find_if(paths.begin(), paths.end(), [&](auto v){ return paths[0].second != v.second; }) - paths.begin();
    if(idx != paths.size()){
        ll cost3 = to_root + paths[0].first + paths[idx].first;
        paths.erase(paths.begin() + idx);
        R[2] = max(R[2], cost3);
        for(int i=1; i<paths.size(); i++) R[i+2] = max(R[i+2], cost3 += paths[i].first);
    }

    for(auto [i,w] : G[root]) if(!U[i]) Go(i);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1; i<N; i++){
        int a, b, c, d; cin >> a >> b >> c >> d; Sum += c + d;
        G[a].emplace_back(b, c); G[b].emplace_back(a, d);
    }
    TreeDP(1);
    Go(1);
    for(int i=2; i<=N; i++) R[i] = max(R[i], R[i-1]);
    cin >> Q;
    for(int i=1,t; i<=Q; i++) cin >> t, cout << Sum - R[t] << "\n";
}