백준22306 트리의 색깔과 쿼리 2

작성일 | In

문제 링크

  • http://icpc.me/22306

사용 알고리즘

  • Small to Large

시간복잡도

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

풀이

Small to Large 연습 문제로 유명한 BOJ 17469 트리의 색깔과 쿼리의 온라인 버전입니다.

각 컴포넌트의 아이디를 관리하면서, 각 정점이 몇 번 컴포넌트에 속한 상태인지 관리합시다. 각 정점이 몇 번 컴포넌트에 속했는지 알고 있다면, std::map 등으로 컴포넌트의 색깔들을 관리할 수 있습니다.

간선이 끊어질 때마다 컴포넌트의 아이디를 갱신하는 작업이 문제인데, 분할되는 두 컴포넌트 중 작은 컴포넌트에 속한 정점들의 아이디만 바꿔주면 Small to Large의 원리로 정점의 아이디는 총 $O(N \log N)$번 바뀌게 됩니다. 실제로 각 컴포넌트의 크기를 직접 구하는 것은 어렵고, 두 컴포넌트에서 모두 DFS를 돌리면서 한쪽이 끝날 때까지만 탐색을 수행하면 됩니다. 아래 코드의 Divide함수를 참고해주세요.

DFS를 하는데 걸리는 시간과 std::map을 이용해 컴포넌트를 관리하는 것 모두 $O(N \log^2 N)$이 걸리므로 전체 시간 복잡도는 $O(N \log^2 N)$입니다.

Dynamic Tree(ex. Euler Tour Tree)를 이용해 컴포넌트의 크기를 amortized $O(\log N)$ 시간에 구하고, std::map 대신 hash table을 사용하면 $O(N \log 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
44
45
46
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using PII = pair<int, int>;

int N, Q, P[101010], C[101010], ID[101010], V[101010], L, pv;
set<int> G[101010];
map<int, int> M[101010];

void Ins(int id, int col){ M[id][col]++; }
void Del(int id, int col){ if(!--M[id][col]) M[id].erase(col); }

void Divide(int a, int b){
    G[a].erase(b); G[b].erase(a);
    int prv = ID[a], now = ++pv;

    stack<PII> stk[2];
    vector<int> nodes[2];
    stk[0].emplace(a, 0); V[a] = now;
    stk[1].emplace(b, 0); V[b] = now;
    while(stk[0].size() && stk[1].size()){
        for(int i=0; i<2; i++){
            int v = stk[i].top().x, c = stk[i].top().y; stk[i].pop();
            nodes[i].push_back(v); V[v] = pv;
            auto it = G[v].lower_bound(c);
            if(it == G[v].end()) continue;
            stk[i].emplace(v, *it + 1);
            if(V[*it] != pv) stk[i].emplace(*it, 0);
        }
    }
    auto &vec = stk[0].empty() ? nodes[0] : nodes[1];
    for(auto i : vec) Del(ID[i], C[i]), Ins(ID[i] = now, C[i]);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> Q; Q += N - 1;
    for(int i=2; i<=N; i++) cin >> P[i], G[P[i]].insert(i), G[i].insert(P[i]);
    for(int i=1; i<=N; i++) cin >> C[i], M[0][C[i]]++;
    for(int i=1; i<=Q; i++){
        int op, a; cin >> op >> a; a ^= L;
        if(op == 1) Divide(P[a], a);
        else cout << (L = M[ID[a]].size()) << "\n";
    }
}

$O(N \log N)$ with Euler Tour Tree

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
143
144
145
146
147
148
149
150
151
/******************************
Author: jhnah917(Justice_Hui)
g++ -std=c++17 -DLOCAL
******************************/

#include <bits/extc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define IDX(v, x) (lower_bound(all(v), x) - v.begin())
using namespace std;

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;
using PII = pair<int, int>;
constexpr ll MAX_N = 101010;

inline ll f(int s, int e){ return s * MAX_N + e; }
namespace splayTree{
    struct SplayNode{
        SplayNode *p, *l, *r;
        int a, b, sz, flag;
        SplayNode() : SplayNode(-1, -1){}
        SplayNode(int a, int b) : a(a), b(b) { l = r = p = nullptr; sz = 1; flag = 0; };
        friend int get_sz(const SplayNode *x) { return x ? x->sz : 0; }
        bool is_left() const { return p && this == p->l; }
        void update(){
            sz = 1 + get_sz(l) + get_sz(r);
        }
        void rotate(){
            if(is_left()) r && (r->p = p), p->l = r, r = p;
            else l && (l->p = p), p->r = l, l = p;
            if(p->p) (p->is_left()? p->p->l : p->p->r) = this;
            auto *t = p; p = t->p; t->p = this;
            t->update(); update();
        }
    };
    void splay(SplayNode *x){
        for(; x->p; x->rotate()){
            if(x->p->p) (x->is_left() ^ x->p->is_left() ? x : x->p)->rotate();
        }
    }
    SplayNode* concat(SplayNode *a, SplayNode *b){
        while(a->r) a = a->r; splay(a);
        a->r = b; b->p = a; a->update();
        return a;
    }
    bool is_same_tree(SplayNode *a, SplayNode *b){
        splay(a); splay(b);
        while(a->p) a = a->p;
        return a == b;
    }
}

struct EulerTourTree{
    vector<splayTree::SplayNode*> nodes;
    unordered_map<ll, splayTree::SplayNode*> edges;
    EulerTourTree(int n) : nodes(n + 1) {
        for(int i=1; i<=n; i++) edges[f(i,i)] = nodes[i] = new splayTree::SplayNode(i, i);
    }
    void reRoot(int v){
        auto x = nodes[v]; splay(x);
        auto xl = x->l, xr = x->r;
        if(!xl || !xr) return;
        x->l = x->r = xl->p = xr->p = nullptr; x->update();
        concat(xr, xl); concat(xl->p, x);
    }
    void link(int u, int v){
        auto x = nodes[u], y = nodes[v];
        reRoot(u); reRoot(v);
        splay(x); splay(y);
        auto e1 = edges[f(u,v)] = new splayTree::SplayNode(u, v);
        auto e2 = edges[f(v,u)] = new splayTree::SplayNode(v, u);
        concat(x, e1); concat(e1, y); concat(e1, e2);
    }
    void cut(int a, int b){
        auto x = edges[f(a,b)], y = edges[f(b,a)];
        splay(x);
        auto xl = x->l, xr = x->r;
        if(xl) xl->p = nullptr;
        if(xr) xr->p = nullptr;
        splay(y);
        auto yl = y->l, yr = y->r;
        bool flag = xl && (xl == y || xl->p);
        if(yl) yl->p = nullptr;
        if(yr) yr->p = nullptr;
        if(flag) yl && xr && concat(yl, xr);
        else xl && yr && concat(xl, yr);
        edges.erase(f(a,b)); edges.erase(f(b,a));
        delete x; delete y;
    }
    bool is_connected(int u, int v){
        return is_same_tree(nodes[u], nodes[v]);
    }
    int size(int v){
        auto x = nodes[v];
        splay(x); return x->sz;
    }
};

int N, Q, P[101010], C[101010], ID[101010];
int Count[101010], pv;
__gnu_pbds::gp_hash_table<int, int> ColorCount[101010];
set<int> G[101010];

void Ins(int id, int col){
    if(!ColorCount[id][col]++) Count[id]++;
}
void Del(int id, int col){
    if(!--ColorCount[id][col]) Count[id]--, ColorCount[id].erase(col);
}

void Coloring(int st, int now){
    int prv = ID[st];
    queue<int> q; q.push(st); ID[st] = now;
    while(q.size()){
        int v = q.front(); q.pop();
        Del(prv, C[v]); Ins(now, C[v]);
        for(auto i : G[v]) if(ID[i] == prv) q.push(i), ID[i] = now;
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> Q; Q += N - 1;
    EulerTourTree ETT(N);
    for(int i=2; i<=N; i++){
        cin >> P[i];
        G[i].insert(P[i]);
        G[P[i]].insert(i);
        ETT.link(P[i], i);
    }
    for(int i=1; i<=N; i++) cin >> C[i], Ins(0, C[i]);

    int lst = 0;
    while(Q--){
        int op, a; cin >> op >> a; a ^= lst;
        if(op == 2){
            lst = Count[ID[a]];
            cout << lst << "\n";
            continue;
        }
        int u = P[a], v = a;
        G[u].erase(v); G[v].erase(u);
        ETT.cut(u, v);
        if(ETT.size(u) < ETT.size(v)) swap(u, v); // v is smaller component
        Coloring(v, ++pv);
    }
}