<div id="readability-page-1" class="page">선택되지 않은 간선의 가중치 합을 최소화하는 문제입니다. 반대로 선택된 간선의 가중치 합을 최대화하는 문제로 생각해서 해결해 봅시다.선택한 정점이 트리의 루트라고 생각합시다. 루트로 올라가는 간선의 가중치를 최소화하는 문제입니다. 
Tree DP를 이용하면 $O(N)$ 전처리를 통해 각 정점이 루트인 경우에 대한 답을 상수 시간에 구할 수 있습니다. 이 문제에 도전할 정도의 실력이라면 다들 알고 있을 것이라 믿습니다.루트를 고정하는 Subtask 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)$입니다. 
한국에서는 <a href="https://www.acmicpc.net/problem/8987">KOI 2013 고등부 4번. 수족관 3</a>의 풀이로도 잘 알려져 있습니다.따라서 두 번째 경우는 $O(N \log N)$ 시간에 처리할 수 있습니다.이제 세 번째 경우를 살펴보겠습니다. 세 번째 경우에서는 두 개 이상의 서로 다른 서브 트리에서 리프 정점을 선택해야 합니다. 한쪽에서만 정점을 뽑으면, 그 서브 트리에서 루트로 올라가는 간선이 선택되지 않을 수 있기 때문입니다. 
사실 세 번째 경우도 두 번째 경우와 비슷하게 처리할 수 있습니다. 각 경로가 어떤 서브 트리에서 유래했는지 함께 저장한 다음, 가장 큰 경로와 다른 서브 트리에서 유래한 가장 큰 경로를 강제로 포함시키면 됩니다. 따라서 세 번째 경우도 $O(N \log N)$ 시간에 처리할 수 있습니다.루트가 고정되어 있을 때 $O(N \log N)$ 만큼 걸리므로 전체 시간 복잡도는 $O(N^2 \log N)$입니다.Subtask 4의 풀이에 Centroid Decomposition을 적용하면 $O(N^2 \log N)$을 $O(N \log^2 N)$으로 줄일 수 있습니다. 
Subtask 4 코드에 센트로이드 관련 처리 부분만 추가하면 됩니다.<div><table><tbody><tr><td><pre>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</pre></td><td><pre><code>#include &lt;bits/stdc++.h&gt;
using namespace std;
using ll = long long;

ll N, Q, Sum, C1, C[202020], R[202020];
vector&lt;pair&lt;ll,ll&gt;&gt; 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 &amp;&amp; !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 &amp;&amp; !U[i] &amp;&amp; S[i]*2 &gt; 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&lt;pair&lt;ll,ll&gt;&gt; PathsFromRoot(int root){
 vector&lt;pair&lt;ll,ll&gt;&gt; paths;
 function&lt;ll(int,int,int)&gt; dfs = [&amp;](int st, int v, int b) -&gt; 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 &gt; 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&lt;pair&lt;ll,ll&gt;&gt; paths = PathsFromRoot(root);
 sort(paths.begin(), paths.end(), greater&lt;&gt;());

 // 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&lt;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(), [&amp;](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&lt;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 &gt;&gt; N;
 for(int i=1; i&lt;N; i++){
 int a, b, c, d; cin &gt;&gt; a &gt;&gt; b &gt;&gt; c &gt;&gt; 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&lt;=N; i++) R[i] = max(R[i], R[i-1]);
 cin &gt;&gt; Q;
 for(int i=1,t; i&lt;=Q; i++) cin &gt;&gt; t, cout &lt;&lt; Sum - R[t] &lt;&lt; "\n";
}
</code></pre></td></tr></tbody></table></div></div>

JusticeHui가 PS하는 블로그

문제 링크
http://icpc.me/17674
문제 출처
2018/2019 JOISC Day3 1번
사용 알고리즘
트리 DP
그리디
센트로이드
시간복잡도
$O(N \log^2 N)$
풀이
선택되지 않은 간선의 가중치 합을 최소화하는 문제입니다. 반대로 선택된 간선의 가중치 합을 최대화하는 문제로 생각해서 해결해 봅시다.
Subtask 2. $Q = 1, E_1 = 1$ (7점)
선택한 정점이 트리의 루트라고 생각합시다. 루트로 올라가는 간선의 가중치를 최소화하는 문제입니다.
코드
Subtask 4. $N \leq 2\,000$ (30점)
루트를 고정하는 Subtask 2의 아이디어는 그대로 가져갑니다. 추가로, 루트 정점과 리프 정점만 선택해도 정답을 찾을 수 있다는 점을 관찰해야 합니다. 리프 정점이 아닌 두 정점을 선택하는 것이 최적이라면, 자식 정점을 대신 선택해도 같거나 더 좋은 답을 낼 수 있다는 점을 생각해 보면 좋습니다.
루트가 고정된 상태에서 정점을 선택하는 것은 세 가지 경우로 나눌 수 있습니다.
루트만 선택 (정점 1개 선택)
루트 정점을 선택하고 리프 정점을 1개 이상 선택
루트 정점을 선택하지 않고 리프 정점을 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$ 밑에서 끊어져서 더 이상 연장되지 않습니다.
KOI 2013 고등부 4번. 수족관 3의 풀이로도 잘 알려져 있습니다.
따라서 두 번째 경우는 $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)$으로 줄일 수 있습니다.
전체 코드
#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";
}

백준17674 특별관광도시

댓글