백준18932 트리와 쿼리 16

작성일 | In

문제 링크

  • http://icpc.me/18932

사용 알고리즘

  • Centroid Decomposition

시간복잡도

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

풀이

1번 쿼리(간선 추가 쿼리)가 모두 주어진 다음 2번 쿼리가 주어지는, 조금 더 쉬운 문제를 생각해봅시다.
이 문제는 단순히 Centroid Tree의 각 정점에서 도달할 수 있는 다른 정점까지 도달하는 거리를 저장하는 것으로 $O(Q \log^2 N)$ 해결할 수 있습니다.

간선 추가 쿼리는 Centroid Decomposition 정보(Centroid Tree)를 Small to Large로 합치면 될 것 같다는 생각을 할 수 있습니다. 구체적으로, 연결해야 하는 두 정점이 속한 Centroid Tree의 루트부터 시작해서, 큰 서브 트리 밑에 작은 서브 트리를 넣어주면 됩니다.
하지만 잘 생각해보면 이 방식을 이용해 Centroid Tree를 합쳐도 최악의 경우에는 선형 시간을 피할 수 없다는 것을 알 수 있습니다.

Centroid Tree가 너무 균형이 안 맞는 경우에는 어쩔 수 없이 Centroid Tree를 다시 구축(rebuild)해야 합니다.

Centroid Tree에서 각 정점을 루트로 하는 서브 트리마다, 그 정점을 루트로 하는 서브 트리가 마지막으로 rebuild 되었을 때의 크기 $L_v$를 저장합시다. 간선 추가 쿼리에 의해 서브 트리가 합쳐질 때, 합친 크기가 $L_v$의 2배 이상이 될 때마다 rebuild하면, 각 서브 트리의 크기는 항상 부모 서브 트리의 $3/4$ 이하가 됩니다. 그러므로 Centroid Tree의 높이를 $O(\log N)$으로 유지할 수 있습니다.

아래 코드는 구현의 편의를 위해서 서브 트리를 합칠 때 부모 서브 트리의 $3/4$ 초과일 때 rebuild하는 방식으로 구현했습니다.

전체 코드

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using PII = pair<int, int>;
constexpr int SZ = 101010, INF = 0xc03f3f3f;

int N, Q, lst;
vector<int> G[SZ];

int S[SZ];
int CP[SZ], CS[SZ], C_LV[SZ], C_ID[SZ]; // c_tree parent, size, level, child id, child cnt
vector<int> Info[SZ];
vector<vector<int>> cInfo[SZ];
map<int, int> D[SZ];

void add(vector<int> &vec, int idx){
    if(idx >= vec.size()) vec.resize(idx+1);
    vec[idx]++;
}
int get(const vector<int> &vec, int idx){
    return 0 <= idx && idx < vec.size() ? vec[idx] : 0;
}

int get_sz(int v, int b=-1){
    S[v] = 1;
    for(auto i : G[v]) if(i == b && C_LV[i] == INF) S[v] += get_sz(i, v);
    return S[v];
}
int get_cent(int v, int tot, int b=-1){
    for(auto i : G[v]) if(i == b && C_LV[i] == INF && S[i]*2 > tot) return get_cent(i, tot, v);
    return v;
}

vector<PII> gather(int v, int b, int lim, int d){
    vector<PII> ret;
    function<void(int,int,int)> dfs = [&ret,&lim,&dfs](int v, int b, int d){
        ret.emplace_back(v, d);
        for(auto i : G[v]) if(i != b && C_LV[i] >= lim) dfs(i, v, d+1);
    };
    dfs(v, b, d);
    return move(ret);
}

int CD(int v, int lv){
    int cent = get_cent(v, get_sz(v));

    CS[cent] = S[v];
    C_LV[cent] = lv;
    Info[cent].clear();
    Info[cent].push_back(1);
    cInfo[cent].clear();
    D[cent].clear();

    int idx = -1;
    for(auto i : G[cent]){
        if(C_LV[i] != INF) continue;
        idx++;
        cInfo[cent].emplace_back();
        for(const auto &j : gather(i, cent, INF, 1)){
            add(Info[cent], j.y);
            add(cInfo[cent][idx], j.y);
            D[cent][j.x] = j.y;
        }

        int nxt = CD(i, lv+1);
        CP[nxt] = cent;
        C_ID[nxt] = idx;
    }
    return cent;
}

void Query1(int a, int b){
    G[a].push_back(b);
    G[b].push_back(a);

    vector<int> a_path, b_path;
    for(int i=a; i!=-1; i=CP[i]) a_path.push_back(i);
    for(int i=b; i!=-1; i=CP[i]) b_path.push_back(i);

    int prv = -1, pIdx = -1;
    while(a_path.size()){
        int a_root = a_path.back(), b_root = b_path.back();
        if(CS[a_root] < CS[b_root]) swap(a, b), swap(a_path, b_path), swap(a_root, b_root);
        a_path.pop_back();

        if(CS[b_root] * 4 > CS[a_root] * 3){
            int lv = C_LV[a_root];
            for(const auto &j : gather(a_root, -1, lv, 0)) C_LV[j.x] = INF;
            int new_cent = CD(a_root, lv);
            CP[new_cent] = prv; C_ID[new_cent] = pIdx;
            return;
        }

        CP[a_root] = prv;
        CS[a_root] += CS[b_root];
        C_ID[a_root] = pIdx;

        int idx;
        if(a_path.size()) idx = C_ID[a_path.back()];
        else idx = cInfo[a_root].size(), cInfo[a_root].emplace_back();

        int d = D[a_root][a] + 1;
        for(const auto &i : gather(b, a, C_LV[b_root], 0)){
            C_LV[i.x]++;
            add(Info[a_root], i.y+d);
            add(cInfo[a_root][idx], i.y+d);
            D[a_root][i.x] = i.y + d;
        }

        prv = a_root; pIdx = idx;
    }
    int bv = b_path.back();
    CP[bv] = prv; C_ID[bv] = pIdx;
}

void Query2(int v, int k){
    int ans = 0;
    for(int i=v, prv=-1; i!=-1; i=CP[i]){
        int d = k - D[i][v];
        ans += get(Info[i], d);
        if(prv != -1) ans -= get(cInfo[i][C_ID[prv]], d);
        prv = i;
    }
    cout << ans << "\n";
    lst = ans;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> Q;
    for(int i=1; i<=N; i++){
        CP[i] = -1; CS[i] = 1; C_ID[i] = -1;
        Info[i].push_back(1);
    }

    for(int i=1; i<=Q; i++){
        int op, a, b; cin >> op >> a >> b;
        if(op == 1) Query1((a + lst) % N + 1, (b + lst) % N + 1);
        else Query2((a + lst) % N + 1, (b + lst) % N);
    }
}