백준7610 Synchronization

작성일 | In

문제 링크

  • http://icpc.me/7610

문제 출처

  • 2013 JOI Open Contest 2번

사용 알고리즘

  • Link Cut Tree

시간복잡도

  • $O((M+Q) \log N)$

풀이

간선 제거 쿼리가 없는 문제를 생각해봅시다.
각 컴포넌트의 “정답”을 루트 정점에 저장하면서, 간선이 추가될 때마다 Union-Find를 이용해 컴포넌트를 합치면 됩니다. 이때 각 컴포넌트의 “정답”은 단순히 컴포넌트의 크기가 됩니다.

간선을 끊는다면? “Link Cut Tree를 쓰면 된다!” 라는 단순하고 명쾌한 해답을 찾을 수 있습니다. Union-Find처럼 각 컴포넌트의 “정답”을 루트 정점에서 관리하면 됩니다.

하지만 간선을 끊는 쿼리와 연결하는 쿼리가 여러 번 주어지면, 두 컴포넌트를 합칠 때 정보의 교집합이 생길 수 있습니다. 이는 트리의 간선이 연결하는 정점 쌍이 바뀌지 않기 때문에 쉽게 처리할 수 있습니다.
간선 $E = (u, v)$가 마지막으로 끊어지기 직전의 컴포넌트 크기 $S(E)$를 알고 있다면, $E$가 다시 트리에 추가될 때 해당 컴포넌트의 “정답”은 $Ans(u)+Ans(v)-S(E)$가 됩니다.

간선을 끊고 붙이고 루트 정점을 구하는 연산은 모두 Link Cut Tree를 이용해 amortized $O(\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
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
#include <bits/stdc++.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())
using namespace std;

typedef long long ll;

struct Node{
    Node *l, *r, *p; int val;
    Node() : Node(1) {}
    Node(int val) : l(nullptr), r(nullptr), p(nullptr), val(val) {}
    bool IsLeft() const { return this == p->l; }
    bool IsRoot() const { return !p || (p->l != this && p->r != this); }
    void Rotate(){
        if(IsRoot()) return;
        if(IsLeft()){
            if(r) r->p = p; p->l = r; r = p;
        }
        else{
            if(l) l->p = p; p->r = l; l = p;
        }
        if(!p->IsRoot()) (p->IsLeft() ? p->p->l : p->p->r) = this;
        auto t = p; p = t->p; t->p = this;
    }
};
void Splay(Node *x){
    for(; !x->IsRoot(); x->Rotate()){
        if(!x->p->IsRoot()){
            if(x->IsLeft() == x->p->IsLeft()) x->p->Rotate();
            else x->Rotate();
        }
    }
}
void Access(Node *x){
    Splay(x); x->r = nullptr;
    for(; x->p; Splay(x)) Splay(x->p), x->p->r = x;
}
void link(Node *p, Node *c){
    Access(c); Access(p);
    c->l = p; p->p = c;
}
void Cut(Node *x){
    Access(x); x->l->p = nullptr; x->l = nullptr;
}
Node* Root(Node *x){
    Access(x); while(x->l) x = x->l;
    Access(x); return x;
}
Node* Par(Node *x){
    Access(x); if(!x->l) return nullptr;
    x = x->l; while(x->r) x = x->r;
    Access(x); return x;
}

int N, M, Q;
int X[202020], Y[202020];

Node nd[202020];
bool chk[202020];
int sum[202020];

void On(int t){
    int a = Root(nd + X[t]) - nd;
    int b = Root(nd + Y[t]) - nd;
    int now = nd[a].val + nd[b].val - sum[t];
    link(nd + X[t], nd + Y[t]);
    a = Root(nd + X[t]) - nd;
    nd[a].val = now;
}
void Off(int t){
    int a = X[t], b = Y[t];
    int rt = Root(nd + a) - nd;
    int now = nd[rt].val;
    if(Par(nd + a) - nd == b) Cut(nd + a);
    else Cut(nd + b);
    sum[t] = now;
    a = Root(nd + a) - nd;
    b = Root(nd + b) - nd;
    nd[a].val = nd[b].val = now;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M >> Q;
    for(int i=1; i<N; i++) cin >> X[i] >> Y[i];
    for(int i=1; i<=M; i++){
        int t; cin >> t; chk[t] ^= 1;
        if(chk[t]) On(t);
        else Off(t);
    }
    for(int i=1; i<=Q; i++){
        int t; cin >> t;
        int rt = Root(nd + t) - nd;
        cout << nd[rt].val << "\n";
    }
}