오랜만의 문제 풀이이다.
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 << ' ';
}
'PS 문제들' 카테고리의 다른 글
[Codeforces] 2028E. Alice's Adventures in the Rabbit Hole (0) | 2024.11.11 |
---|---|
[UCPC 2023 예비소집] 계단 자르기 (0) | 2024.11.01 |
5월 알고리즘 (4) | 2024.06.16 |
[2022 Yokohama Regional] Make a Loop (BOJ 27421) (3) | 2023.11.08 |
[NYPC 2022 Round 2-A] 로봇 청소기 ★ (0) | 2023.10.24 |