백준18477 Jiry Matchings

작성일 | In

문제 링크

  • http://icpc.me/18477

문제 출처

  • 300iq Contest 2 J번

사용 알고리즘

  • HLD
  • Tree DP
  • 분할 정복

시간복잡도

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

풀이

간선에 가중치가 있는 트리가 주어졌을 때, 매칭을 1개, 2개, 3개, … , N-1개 골랐을 때 가중치 합의 최대를 구하는 문제입니다.

MCMF

트리는 이분 그래프입니다. 이분 그래프에서 매칭 K개 골랐을 때 가중치 합의 최대/최소는 MCMF를 이용해 구해줄 수 있습니다.
유량을 1씩 계속 흘려보내는 방식으로 $O(N^3)$에 정답을 구할 수 있습니다. 물론 매우 느립니다.

MCMF로 답을 구할 수 있다는 것은, 답이 K에 대해 볼록하다는 것을 의미합니다.
다시 말해, 가로축을 매칭의 개수, 세로 축을 가중치의 합의 최댓값이라고 하면 아래 그래프처럼 볼록하게 나오게 됩니다.

이 성질을 이용해 풀이를 발전시켜 봅시다.

Tree DP

트리니까 트리DP를 생각해볼 수 있습니다.
$D0(N, K)$를 N을 루트로 하는 서브트리에서 K개의 매칭을 골랐을 때 최대 가중치라고 정의합시다.
$D1(N, K)$는 N을 루트로 하는 서브트리 안에서 K-1개의 매칭을 고르고, N은 N의 부모 정점과 매칭시켰을 때 최대 가중치라고 정의합시다.

상태 전이가 다소 복잡합니다.
D0(N, K)를 만들기 위해서는 자식 $c_1, c_2, \dots , c_t$가 있을 때 각 자식의 서브트리에서 총 K개의 매칭을 선택해서 $D0(c_i, k_i)$를 다 더해주거나, t-1개는 $D(c_i, k_i)$를 선택하고 나머지 1개는 $D1(c_i, k_i)$를 더한 값 중에 최댓값이 됩니다.
전자는 N의 자식들이 모두 N과 매칭되지 않은 것을 의미하고, 후자는 자식들 중 한 개가 N과 매칭된 것을 의미합니다.

D1(N, K)를 만드는 것은 D0(N, K)를 만드는 것에서 전자의 경우만 고려하면 됩니다. 후자의 경우는 이미 N이 N의 부모와 매칭되어 있기 때문에 반영하면 안 됩니다.
구현은 어떻게 할까요?

O(N^2)

상태 전이를 잘 생각해보면, 각 서브트리에서 아래 그림과 같은 볼록 껍질같은 것을 갖고 있을 때, 두 서브트리의 볼록 껍질을 잘 병합해서 새로운 볼록 껍질을 만드는 것이라고 볼 수 있습니다.
두 볼록 껍질을 합치는 것은, merge sort 하듯이 기울기 순서를 잘 맞춰서 병합해주면 됩니다.

두 서브트리의 볼록 껍질을 합치는 것은 $O(sz[u] + sz[v])$ 시간이 걸립니다.
dfs 돌면서 리프노드부터 쭉 병합해주면 $O(N^2)$에 문제를 해결할 수 있습니다. 더 빠르게 계산해야 합니다.

O(N \log^2 N)

Heavy Light Decomposition을 생각해봅시다. HLD에서 light edge를 타고 올라가면 항상 트리의 크기가 2배 이상이 됩니다.

$O(N^2)$ 풀이처럼 서브트리를 병합할 건데, light edge와 heavy edge를 따로 처리할 것입니다.
먼저 부모와 light edge로 연결된 리프 정점들을 부모 정점에 병합시켜 줍시다.

이렇게 해주면 리프 정점은 모두 heavy chain에 속하게 됩니다. 리프 정점이 속한 heavy chain을 한 번에 병합을 해줍시다.

다시 light edge로 연결된 리프 정점들을 부모 정점에 붙여주고, heavy chain을 한 번에 합쳐주는 과정을 정점이 하나 남을 때까지 해주면 됩니다.
정점을 합칠 때 대충 합치면 당연히 로그 제곱이 보장이 안 됩니다. 분할 정복 느낌으로 2개씩 합쳐주고, 그 결과를 2개씩 합쳐주고, 그 결과를 다시 2개씩 합쳐주고… 해주면 $O(N \log^2 N)$에 풀 수 있습니다.

구현이 정말 귀찮고, 처리해야할 것도 많아서 풀기 어렵습니다.
구현 방법을 글로 풀어쓰는 것도 힘드네요…

구현 방법

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
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;
const ll inf = 1e18;

int n;
vector<p> g[202020];

namespace HLD{
    //대충 HLD를 한다.
}

vector<ll> add_matching(const vector<ll> &vec, ll x){
    //가중치 x짜리 매칭을 추가하면?
    //y절편으로 x만큼 이동하고, 오른쪽으로 한 칸씩 shift
}

vector<ll> merge_slope(vector<ll> a, vector<ll> b){
    //기울기 순으로 정렬되도록 잘 합치자.
}

vector<ll> get_max(const vector<ll> &a, const vector<ll> &b){
    //각 i에 대해 a[i]와 b[i] 중 큰 것을 취하자.
}

void heavy_chain_merge(int v){
    //v부터 시작하는 heavy chain들을 합친다.
}

void node_merge(int v){
    //1. v와 light edge로 연결된 자식들을 모아주자.
    //2. 1에서 모은 정점을 light_child하면, light_child를 순회하면서
        //light_child[i]에서 시작하는 heavy_chain을 먼저 다 합쳐서 light_child[i]에 병합을 한다.
    //3. light_child들을 v에 병합한다.
}

int main(){
    //화이팅!
}