알고리즘 블로그
Published 2024. 10. 2. 01:07
[BOJ 29203] 테마파크 PS 문제들

오랜만의 문제 풀이이다.

KSAAC 2023 summer에 출제된 테마파크 문제이다.

 

$s$의 서브트리를 기준으로, 어떤 두 간선도 조상-후손 관계에 있지 않은 간선 집합들을 관리해두면, $s$와 부모를 잇는 간선과 비교해서 써먹을 수 있을 것 같다. $s$와 부모를 잇는 간선에서의 비용을 $w_s$라고 하자. 당연히 $s\ge 1$일 때만 정의할 수 있다.

 

서브트리 속 여러 정보를 효율적으로 관리하는 것은 보통 스몰투라지 기법이 잘 먹힌다.

 

풀이를 조금 더 구체화해보자.

 

우선, 각 정점은 자신보다 윗쪽에 있는 간선들과 교류가 생기므로 일반적으로 트리 문제를 풀 때 $s$의 서브트리에 정점 $s$를 포함하는 것과는 달리, 정점 $s$는 제거하는 식으로 값들을 정의하자.

 

$\ell_s:=$ 정점 집합 $s^\downarrow \setminus \{s\}$에서 비용 합이 최대인 반사슬 (단, 반사슬의 모든 정점은, 자신을 포함한 자신의 서브트리에 방문해야 하는 정점이 하나는 존재함. 즉, 전혀 쓸데없는 간선은 애초에 포함시키지 않는다는 것)

 

정의가 좀 길고 장황하지만, 대충 써야 하긴 하는데... 그중에서 가성비가 제일 나쁜 것들로 반사슬을 골랐다고 생각하는거다.

 

그러면, 이 반사슬은 $w_s$ 하나와 비교를 통해 무효화 시킬 수 있게 된다.

 

그런데 이 과정을 깊게 생각해보면, 반사슬 하나를 무효화 시킨 후에 다른 반사슬들도 언젠가 시기 적절히 무효화 시켜야 할 것 같다. 따라서 다음과 같은 것을 정의하자.

 

$\mathcal L_s:={\ell_1,\ell_2,\ldots}$는 정점이 겹치지 않는 반사슬들을 가성비 안 좋은 것부터 잘 뽑아 나열한 집합. $\ell_i$의 비용 총합은 $\ell_j$ 비용 총합보다 크거나 같다.

 

이것을 잘 관리하면, 정점 $s$의 자식 $c_1,c_2,\ldots,c_k$에 대해 $\mathcal L_{c_1},\mathcal L_{c_2},\ldots,\mathcal L_{c_k}$에서 제일 앞선 반사슬들을 하나씩 뽑아 묶으면 새로운 반사슬 집합 $\mathcal L_s$를 구성할 수 있다. 또한 $s$가 방문해야 하는 정점이라면, 새로운 반사슬 $\{s\}$를 $\mathcal L_s$에 추가할 수 있다.

 

최댓값 참조/추가/삭제만이 필요하므로 std::priority_queue를 활용하여 구현하면 매우 효율적일 것이다. 그렇게 잘 구현하면 정답을 구할 수 있는데, 사실 여기서 끝이 아니다.

 

이 문제는 알고 보면 스페셜 저지 문제다... 따라서 $\mathcal L_s$의 구체적인 반사슬의 구성 정점들까지 한꺼번에 관리해야 한다. 이는 독립적인 스몰투라지로 구동하거나 혹은 간단히 std::list를 이용하여 처리할 수 있다. 이 파트가 까다롭고 어렵긴 하지만, 스몰투라지에 대한 내공을 늘릴 수 있게 된다고 본다.

 

#include <bits/stdc++.h>
#define rep(i,a,b) for (int i = (a); i <= (b); ++i)
using namespace std; using ll = long long;

const int N = 2e5+3;
int n, m;
bool pay[N];
vector<array<int,3>> adj[N];

struct Layer {
    ll sum;
    list<int> *elements;
    bool operator < (const Layer &rhs) const {
        return sum < rhs.sum;
    }
    Layer(): sum(0), elements(nullptr) {}
    Layer(ll _s, list<int> *_l): sum(_s) {
        elements = _l;
    }
};

priority_queue<Layer> *L[N];

void erase(vector<array<int,3>> &v, int x) {
    for (auto it = v.begin(); it != v.end(); it++) {
        if (it->at(0) == x) {
            v.erase(it);
            return;
        }
    }
}

void merge(Layer &x, Layer &y) { // anyway, make x correct
    x.sum += y.sum;
    auto &X = *x.elements;
    X.splice(end(X), *y.elements);
}

auto merge(auto x, auto y) // make x correct
{
    if (x->size() < y->size()) swap(x,y);
    vector<Layer> upd_layers(y->size());
    for (auto &l1 : upd_layers) {
        l1 = x->top(), x->pop();
        auto l2 = y->top();
        merge(l1, l2), y->pop();
    }
    for (auto &l : upd_layers) x->push(l);
    return x;
}

void dfs(int s=1, int e=0) {
    for (auto [u,w,i] : adj[s]) if (u!=e)
    {
        dfs(u,s);
        
        if (pay[u]) {
            L[u]->push({w,new list<int>{i}});
        }
        else if (L[u]->size() > 0) {
            if (L[u]->top().sum > w) {
                L[u]->pop();
                L[u]->push({w,new list<int>{i}});
            }
        }
    }
    erase(adj[s], e);
    
    L[s] = new priority_queue<Layer>();
    
    for (auto [u,w,i] : adj[s]) {
        L[s] = merge(L[s], L[u]);
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    rep(i,1,m) {
        ll x; cin >> x;
        pay[x] = 1;
    }
    rep(i,1,n-1) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v,w,i});
        adj[v].push_back({u,w,i});
    }
    
    dfs();
    
    ll ans1=0;
    list<int> ans2;
    
    while (L[1]->size() > 0)
    {
        ans1 += L[1]->top().sum;
        ans2.splice(end(ans2), *L[1]->top().elements);
        L[1]->pop();
    }
    
    cout << ans1 << '\n' << size(ans2) << '\n';
    for (auto e : ans2) cout << e << ' ';
}
profile

알고리즘 블로그

@도훈.

포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!

profile on loading

Loading...