解題區/出題解題

動態樹 樹形避難所

contents

  1. 1. 樹形避難所 I
  2. 2. 樹形避難所 II
  3. 3. 分析
  4. 4. 延伸問題
  5. 5. 參考解答
    1. 5.1. 樹形避難所 I
    2. 5.2. 樹形避難所 II

題目描述請至 Zerojudge e003: 樹形避難所 I、e004: 樹形避難所 II 查閱詳細內容

樹形避難所 I

在一個樹形避難所中有 $N$ 個房間，待在充滿監視器房間的你，透過監視器的顯示發現存在一些未知的入侵者出現在某些房間。為了保護同伴，你可以選擇開啟或關閉房間之間的通道，而你也會收到來自於某個房間的同伴求救訊號，此時給予所有可能遇見的入侵者數量，以便同伴做好萬全的作戰準備。然而，操縱通道的控制器已不受限制，你只能眼睜睜地看著同伴與入侵者對抗，現在的你 … 做好準備了嗎？

  • 操作 1 $u$ $v$：將房間 $u$ 與 $v$ 的通道開啟
  • 操作 2 $u$ $v$：將房間 $u$ 與 $v$ 的通道關閉
  • 操作 3 $u$ $w$：更正房間 $u$ 為 $w$ 個入侵者
  • 操作 4 $u$：回答來自 $u$ 的求救信號，告知與其可能面臨到的入侵者個數

樹形避難所 II

由於上一個樹形避難所已經不再安全，全員轉移到下一個避難所，新的地方將不再是先前的平面構造，新的避難所建構在地下水層中，每一個房間可以在水中移動，並且打通到上一層的某一個房間。不幸地，新的入侵者更加地難纏，想保護大家的你，想藉由破壞某一個房間，將其相連的下層房間的入侵者一同殲滅，情局不斷地變化，哪一個才是最好的破壞手段呢 …

  • 操作 1 $u$ $v$：將房間 $u$ 與上層房間 $v$ 的通道開啟
  • 操作 2 $u$：關閉房間 $u$ 與上層的通道
  • 操作 3 $u$ $w$：更正房間 $u$ 為 $w$ 個入侵者
  • 操作 4 $u$：估算摧毀房間 $u$，可以殲滅的入侵者個數

分析

這一題對於樹的操作，牽涉到修改邊，修改點權，詢問整個連通的樹大小、以及子樹大小。可以考慮使用 Link/Cut Tree 完成。也有高手使用了離線算法，對操作分治後計算答案，將一個邊的存在時間記錄在某個時間戳記上，整體落在 $\mathcal{O}(M \log M)$，由上而下合併所有存在的邊來完成單一詢問，需要搭配啟發式合併，來指查找根造成的退化，這一點相當地聰明。若強制在線，仍需要使用動態樹完成之。

對於第一題，只有包含前三個操作，可以當作一個無根樹操作，因此在 LCT 中的 $\text{MakeRoot}$ 打上反轉標記，無視原本的父子關係，額外維護一個虛邊上的子樹大小，如此一來就可以計算整個子樹大小。其餘的點權修改就相較於容易許多。對於第二題，便要求有根樹，因此在轉到根節點時，不能打上反轉標記，此時的左子樹為父節點，扣除掉父節點的大小後，便可以得到子樹大小。

  • 動態樹解法：空間複雜度 $\mathcal{O}(N)$，操作複雜度 $\text{Amortized} \; \mathcal{O}(\log N)$
  • 離線解法：空間複雜度 $\mathcal{O}(M \log M)$，整體時間複雜度 $\mathcal{O}(M \log M)$

延伸問題

如果子樹存在等價關係，意即他們會被一個操作同時受到影響，那麼更新會退化嗎？

如果這個問題能被解決，那麼使用相同的概念，便能解決更多的高壓縮架構問題。工作就能輕鬆一些了。

參考解答

樹形避難所 I

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
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#include <bits/stdc++.h>
using namespace std;
  
class LCT { // Link-Cut Tree
public:
    static const int MAXN = 30005;
    struct Node;
    static Node *EMPTY;
    static Node _mem[MAXN];
    static int bufIdx;
    struct Node {
        Node *ch[2], *fa;
        int rev;
        int vsize, size, val;
        void init() {
            ch[0] = ch[1] = fa = NULL;
            size = 0, vsize = 0, rev = 0;
        }
        bool is_root() {
            return fa->ch[0] != this && fa->ch[1] != this;
        }
        void pushdown() {
        	if (rev) {
        		ch[0]->rev ^= 1;
                ch[1]->rev ^= 1;
        		swap(ch[0], ch[1]);
        		rev = 0;
            }
        }
        void pushup() {
        	if (this == EMPTY)
        		return;
        	size = ch[0]->size + ch[1]->size + val + vsize;
        }
    };
    LCT() {
        EMPTY = &_mem[0];
        EMPTY->fa = EMPTY->ch[0] = EMPTY->ch[1] = EMPTY;
        EMPTY->size = 0;
        bufIdx = 1; 
    }
    void init() {
        bufIdx = 1;
    }
    Node* newNode() {
        Node *u = &_mem[bufIdx++];
        u->init();
        u->fa = u->ch[0] = u->ch[1] = EMPTY;
        return u;
    }
    void rotate(Node *x) {
        Node *y;
        int d;
        y = x->fa, d = y->ch[1] == x ? 1 : 0;
        x->ch[d^1]->fa = y, y->ch[d] = x->ch[d^1];
        x->ch[d^1] = y;
        if (!y->is_root())
            y->fa->ch[y->fa->ch[1] == y] = x;
        x->fa = y->fa, y->fa = x;
        y->pushup(), x->pushup();
    }
    void deal(Node *x) {
        if (!x->is_root())   deal(x->fa);
        x->pushdown();
    }
    void splay(Node *x) {
        Node *y, *z;
        deal(x);
        while (!x->is_root()) {
            y = x->fa, z = y->fa;
            if (!y->is_root()) {
                if (y->ch[0] == x ^ z->ch[0] == y)
                    rotate(x);
                else
                    rotate(y);
            }
            rotate(x);
        }
        x->pushdown();
    }
    Node* access(Node *u) {
        Node *v = EMPTY;
        for (; u != EMPTY; u = u->fa) {
            splay(u);
            u->vsize += u->ch[1] != EMPTY ? u->ch[1]->size : 0;
            u->vsize -= v != EMPTY ? v->size : 0;
            u->ch[1] = v;
            u->pushup();
            v = u;
        }
        return v;
    }
    void mk_root(Node *u) {
        access(u)->rev ^= 1, splay(u);
    }
    void cut(Node *x, Node *y) {
    	mk_root(x);
    	access(y), splay(y);
//    	debug(10);
    	assert(y->ch[0] == x);
        y->ch[0] = x->fa = EMPTY;
        y->pushup();
    }
    void link(Node *x, Node *y) {
    	mk_root(y);
    	access(x), splay(x);
        y->fa = x;
        x->vsize += y->size;
        x->pushup();
    }
    Node* find(Node *x) {
        access(x), splay(x);
        for (; x->ch[0] != EMPTY; x = x->ch[0]);
        return x;
    }
    void set(Node *x, int val) {
    	mk_root(x);
    	x->val = val;
    	x->pushup();
    }
    int get(Node *u) {
    	mk_root(u);
    	return u->size;
    }
    int same(Node *x, Node *y) {
        return find(x) == find(y);
    }
    void debug(int n) {
        return;
        puts("==================");
        for (int i = 1; i <= n; i++) {
            Node *u = &_mem[i];
            printf("[%d] %d, %d %d, %d %d %d\n", i, u->fa-_mem, u->ch[0]-_mem, u->ch[1]-_mem, u->size, u->vsize, u->val);
        }
    }
} lct;
LCT::Node *LCT::EMPTY, LCT::_mem[LCT::MAXN];
int LCT::bufIdx;
LCT::Node *node[LCT::MAXN];
int main() {
    int n, m;
    while (scanf("%d %d", &n, &m) == 2) {
        lct.init();
        int cmd, u, v, w;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &w);
            node[i] = lct.newNode();
            lct.set(node[i], w);
        }
        for (int i = 0; i < m; i++) {
            scanf("%d", &cmd);
            if (cmd == 1) {
                scanf("%d %d", &u, &v);
                lct.link(node[u], node[v]);
            } else if (cmd == 2) {
                scanf("%d %d", &u, &v);
                lct.cut(node[u], node[v]);
            } else if (cmd == 3) {
                scanf("%d %d", &u, &w);
                lct.set(node[u], w);
            } else if (cmd == 4) {
                scanf("%d", &u);
                int p = lct.get(node[u]);
                printf("%d\n", p);
            } else {
                scanf("%d %d", &u, &v);
                int f = lct.same(node[u], node[v]);
                printf("%d\n", f);
            }
            lct.debug(10);
        }
    }
    return 0;
}

樹形避難所 II

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
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
#include <bits/stdc++.h>
using namespace std;
  
class LCT { // Link-Cut Tree
public:
    static const int MAXN = 30005;
    struct Node;
    static Node *EMPTY;
    static Node _mem[MAXN];
    static int bufIdx;
    struct Node {
        Node *ch[2], *fa;
        int vsize, size, val;
        void init() {
            ch[0] = ch[1] = fa = NULL;
            size = 0, vsize = 0;
        }
        bool is_root() {
            return fa->ch[0] != this && fa->ch[1] != this;
        }
        void pushdown() {
        }
        void pushup() {
        	if (this == EMPTY)
        		return;
        	size = ch[0]->size + ch[1]->size + val + vsize;
        }
    };
    LCT() {
        EMPTY = &_mem[0];
        EMPTY->fa = EMPTY->ch[0] = EMPTY->ch[1] = EMPTY;
        EMPTY->size = 0;
        bufIdx = 1; 
    }
    void init() {
        bufIdx = 1;
    }
    Node* newNode() {
        Node *u = &_mem[bufIdx++];
        u->init();
        u->fa = u->ch[0] = u->ch[1] = EMPTY;
        return u;
    }
    void rotate(Node *x) {
        Node *y;
        int d;
        y = x->fa, d = y->ch[1] == x ? 1 : 0;
        x->ch[d^1]->fa = y, y->ch[d] = x->ch[d^1];
        x->ch[d^1] = y;
        if (!y->is_root())
            y->fa->ch[y->fa->ch[1] == y] = x;
        x->fa = y->fa, y->fa = x;
        y->pushup(), x->pushup();
    }
    void deal(Node *x) {
        if (!x->is_root())   deal(x->fa);
        x->pushdown();
    }
    void splay(Node *x) {
        Node *y, *z;
        deal(x);
        while (!x->is_root()) {
            y = x->fa, z = y->fa;
            if (!y->is_root()) {
                if (y->ch[0] == x ^ z->ch[0] == y)
                    rotate(x);
                else
                    rotate(y);
            }
            rotate(x);
        }
        x->pushdown();
    }
    Node* access(Node *u) {
        Node *v = EMPTY;
        for (; u != EMPTY; u = u->fa) {
            splay(u);
            u->vsize += u->ch[1] != EMPTY ? u->ch[1]->size : 0;
            u->vsize -= v != EMPTY ? v->size : 0;
            u->ch[1] = v;
            u->pushup();
            v = u;
        }
        return v;
    }
    void mk_root(Node *u) {
        access(u), splay(u);
    }
    void cut(Node *x) {
    	access(x), splay(x);
    	x->ch[0]->fa = EMPTY;
        x->ch[0] = EMPTY;
        x->pushup();
    }
    void link(Node *x, Node *y) {
    	access(x), splay(x);
    	access(y), splay(y);
        x->fa = y;
        y->vsize += x->size;
        y->pushup();
    }
    Node* find(Node *x) {
        access(x), splay(x);
        for (; x->ch[0] != EMPTY; x = x->ch[0]);
        return x;
    }
    void set(Node *x, int val) {
    	mk_root(x);
    	x->val = val;
    	x->pushup();
    }
    int get(Node *u) {
    	mk_root(u);
    	int ret = u->size;
    	if (u->ch[0] != EMPTY)
    		ret -= u->ch[0]->size;
    	return ret;
    }
    int same(Node *x, Node *y) {
        return find(x) == find(y);
    }
    void debug(int n) {
        return;
        puts("==================");
        for (int i = 1; i <= n; i++) {
            Node *u = &_mem[i];
            printf("[%d] %d, %d %d, %d %d %d\n", i, u->fa-_mem, u->ch[0]-_mem, u->ch[1]-_mem, u->size, u->vsize, u->val);
        }
    }
} lct;
LCT::Node *LCT::EMPTY, LCT::_mem[LCT::MAXN];
int LCT::bufIdx;
    LCT::Node *node[LCT::MAXN];
int main() {
    int n, m;
    while (scanf("%d %d", &n, &m) == 2) {
        lct.init();
        int cmd, u, v, w;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &w);
            node[i] = lct.newNode();
            lct.set(node[i], w);
        }
        for (int i = 0; i < m; i++) {
            scanf("%d", &cmd);
            if (cmd == 1) {
                scanf("%d %d", &u, &v);
                lct.link(node[u], node[v]);
            } else if (cmd == 2) {
                scanf("%d", &u);
                lct.cut(node[u]);
            } else if (cmd == 3) {
                scanf("%d %d", &u, &w);
                lct.set(node[u], w);
            } else if (cmd == 4) {
                scanf("%d", &u);
                int p = lct.get(node[u]);
                printf("%d\n", p);
            } else {
                scanf("%d %d", &u, &v);
                int f = lct.same(node[u], node[v]);
                printf("%d\n", f);
            }
            lct.debug(4);
        }
    }
    return 0;
}