백준26415 Ghost

작성일 | In

문제 링크

  • http://icpc.me/26415

사용 알고리즘

  • 트리 디컴포지션

시간복잡도

  • $O(N)$

풀이

halin graph의 treewidth가 3 이하인 tree decomposition을 구하는 문제입니다.

트리의 가장 왼쪽 리프 정점 $l$과 오른쪽 리프 정점 $r$이 연결되어야 하므로, $l, r$을 모두 포함하는 bag이 존재해야 합니다. 각 정점 $v$를 루트로 하는 서브 트리의 tree decomposition에서, 루트 정점의 bag에 $(v, l, r)$을 저장하는 방식으로 만들어 봅시다.

$v$가 리프 정점이면 $l=r=v$입니다. 따라서 $(v, v, v)$를 만들면 됩니다.

이제 $v$가 한 개 이상의 자식 정점을 갖고 있는 경우를 생각해 봅시다. $v$는 $v$의 자식 정점 $c$와 연결되어 있으므로 $v, c$를 포함하는 bag이 존재해야 합니다. $(c,l,r)$의 부모 정점으로 $(v,l,r,c)$를 달면 됩니다. $c$와 연결된 모든 정점을 처리했으므로 더 이상 $c$를 신경쓸 필요가 없다는 것에 주목합시다.
남은 것은 자식 정점의 정보 $(v,l_1,r_1,c_1), (v,l_2,r_2,c_2), \cdots, (v,l_k,r_k,c_k)$가 주어졌을 때, 이 정보들을 하나의 정보 $(v, l, r)$로 합치는 것 뿐입니다. 인접한 두 서브 트리를 합치는 방식으로 진행합니다.

$(v,s,e,c_1)$과 $(v,l,r,c_2)$를 합치는 방법을 생각해 봅시다. $c_1,c_2$를 무시할 수 있으므로 dummy를 의미하는 $d_1,d_2$로 치환해서 $(v,s,e,d_1), (v,l,r,d_2)$로 표기하겠습니다.
왼쪽 서브 트리의 오른쪽 리프 정점 $e$는 오른쪽 서브 트리의 왼쪽 리프 정점 $l$과 연결되어야 합니다. $(v,s,e,d_1) \rightarrow (v,s,e,l)$을 만들어 봅시다. $e$와 연결된 모든 정점을 처리했기 때문에 이제부터 $e$를 무시할 수 있습니다.
지금 만든 bag인 $(v,s,e,l)$과 두 번째 서브 트리를 담당하는 bag인 $(v,l,r,d_2)$ 모두 $l$을 포함하고 있기 때문에, 두 bag은 $l$을 포함하는 bag들로 연결되어야 합니다. $(v,s,r,l)$을 만들어서 두 bag과 연결하면 됩니다. 이제 $l$도 무시할 수 있습니다.
합쳐진 두 서브 트리의 왼쪽 리프 정점인 $s$와 오른쪽 리프 정점인 $r$이 같은 bag에 포함되었으므로 두 서브 트리를 성공적으로 합쳐졌습니다. 또한 4번째 원소는 무시해도 되는 정점이기 때문에 이 절차를 반복해서 모든 서브 트리를 합칠 수 있습니다.

서브 트리를 모두 합치면 $(v,l,r,d)$ 꼴의 bag 하나를 얻을 수 있습니다. 최종적으로 원하는 결과는 $(v,l,r)$이므로 $(v,l,r,d)$의 부모 bag $(v,l,r)$을 만들어서 연결합시다.

이 과정을 구현하면 $O(N)$ 시간에 treewidth가 3인 tree decomposition을 구할 수 있습니다.

전체 코드

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

struct Container{
    vector<int> par;
    vector<vector<int>> bags;
    Container(const vector<int> &par, const vector<vector<int>> &bags) : par(par), bags(bags) {}
};

// vertices are labelled by pre-order
Container HalinDecompose(int n, int root, const vector<vector<int>> &gph){
    vector<int> par;
    vector<vector<int>> bags;
    auto make_node = [&](int parent, vector<int> children, vector<int> bag) -> int {
        int node_id = bags.size();
        for(auto child : children) par[child] = node_id;
        par.push_back(parent); bags.push_back(bag);
        return node_id;
    };

    // return id of bag {vertex, left_leaf, right_leaf}
    function<int(int)> dfs = [&](int v) -> int {
        // leaf: {v, v, v}
        if(gph[v].empty()) return make_node(-1, {}, {v, v, v});

        vector<int> children_bag(gph[v].size());

        // 1. get subtree info: {c, l, r}
        // 2. connect c with v: {c, l, r} -> {v, l, r, c}
        // from now, we can ignore c
        for(int i=0; i<gph[v].size(); i++){
            int c = gph[v][i], sub = dfs(c);
            int l = bags[sub][1], r = bags[sub][2];
            children_bag[i] = make_node(-1, {sub}, {v, l, r, c});
        }

        // merge two adjacent subtree {v, s, e, dummy1} and {v, l, r, dummy2}
        // 1. connect e with l: {v, s, e, d} -> {v, s, e, l}
        // 2. drop e and keep l condition: {v, s, e, l} -> {v, s, r, l}
        //                                 {v, l, r, d} /
        // from now, we can ignore l
        int res = children_bag[0];
        for(int i=1; i<children_bag.size(); i++){
            int nxt = children_bag[i];
            int s = bags[res][1], e = bags[res][2];
            int l = bags[nxt][1], r = bags[nxt][2];
            int conn = make_node(-1, {res}, {v, s, e, l});
            res = make_node(-1, {conn, nxt}, {v, s, r, l});
        }

        // {v, l, r, dummy} -> {v, l, r}
        return make_node(-1, {res}, {v, bags[res][1], bags[res][2]});
    };

    int rt = dfs(root);
    for(auto &bag : bags){
        sort(bag.begin(), bag.end());
        bag.erase(unique(bag.begin(), bag.end()), bag.end());
    }
    return {par, bags};
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int N; cin >> N;
    vector<vector<int>> G(N);
    for(int i=1,p; i<N; i++) cin >> p, G[--p].push_back(i);
    auto [par,bags] = HalinDecompose(N, 0, G);

    cout << bags.size() << "\n";
    for(const auto &bag : bags){
        cout << bag.size() << " ";
        for(int i=0; i<bag.size(); i++) cout << bag[i] + 1 << " \n"[i+1==bag.size()];
    }
    for(int i=0; i<par.size(); i++) if(par[i] != -1) cout << par[i] + 1 << " " << i + 1 << "\n";
}