解題區/解題區 - UVa

UVa 13101 - Tobby on Tree

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

一場遊戲有 $N$ 個數，每一次挑兩個不同的數，將大的數字扣除小的數字，直到沒辦法挑出任何不同的數，亦即所有數皆相同，遊戲結果就是最後的數字值。

現在給予一棵樹，操作有兩種：

  • 詢問樹上兩點 $u$ 到 $v$ 的路徑上的數字，遊戲結果為何。
  • 改變樹上某個節點 $u$ 的值為 $c$。

Sample Input

1
2
3
4
5
6
7
8
9
10
5
5 15 20 15 9
0 2
0 3
3 1
3 4
3
1 2 1
2 3 3
1 1 4

Sample Output

1
2
5
3

Solution

明顯地答案就是路徑上所有數字的最大公因數，充分利用 Link/Cut 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
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
#include <bits/stdc++.h> 
using namespace std;
class LCT { // Link-Cut Tree
public:
    static const int MAXN = 262144;
    struct Node {
        static Node *EMPTY;
        Node *ch[2], *fa;
        int rev;
        int val, size;
        int gcd;
        Node() {
            ch[0] = ch[1] = fa = NULL;
            rev = 0;
            val = 0;
            gcd = 1, size = 1;
        }
        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 ^= 1;
            }
        }
        void pushup() {
            if (this == EMPTY)	return ;
            gcd = this->val, size = 1;
            if (ch[0] != EMPTY) {
            	gcd = __gcd(gcd, ch[0]->gcd);
                size += ch[0]->size;
            }
            if (ch[1] != EMPTY) { 
                gcd = __gcd(gcd, ch[1]->gcd);
                size += ch[1]->size;
            } 
        }
    } _mem[MAXN];
    
    int bufIdx;
    LCT() {
        Node::EMPTY = &_mem[0];
        Node::EMPTY->fa = Node::EMPTY->ch[0] = Node::EMPTY->ch[1] = Node::EMPTY;
        Node::EMPTY->size = 0;
        bufIdx = 1; 
    }
    void init() {
        bufIdx = 1;
    }
    Node* newNode() {
        Node *u = &_mem[bufIdx++];
        *u = Node();
        u->fa = u->ch[0] = u->ch[1] = Node::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->pushup();
    }
    Node* access(Node *u) {
        Node *v = Node::EMPTY;
        for (; u != Node::EMPTY; u = u->fa) {
            splay(u);
            u->ch[1] = v;
            v = u;
            v->pushup();
        }
        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);
        y->ch[0] = x->fa = Node::EMPTY;
    }
    Node* _cut(Node *rt, Node *x) {
        Node *u, *v;
        mk_root(rt);
        access(x), splay(x);
        for (v = x->ch[0]; v->ch[1] != Node::EMPTY; v = v->ch[1]);
        x->ch[0]->fa = x->fa;
        x->fa = x->ch[0] = Node::EMPTY;
        return v;
    }
    void link(Node *x, Node *y) {
        mk_root(x);
        x->fa = y;
    }
    Node* find(Node *x) {
        for (x = access(x); x->pushdown(), x->ch[0] != Node::EMPTY; x = x->ch[0]);
        return x;
    }
    //
    int gcdPath(Node *x, Node *y) {
        mk_root(x);
        access(y), splay(y);
        return y->gcd;
    }
    // 
    void changeNode(Node *x, int c) {
    	mk_root(x);
    	x->val = c;
    }
    void debug(int n) {
    }
} tree;
LCT::Node *LCT::Node::EMPTY;
LCT::Node *A[262144];
int W[131072];
int main() {
    int n, m, cmd, x, y;
    while (scanf("%d", &n) == 1) {
        for (int i = 0; i < n; i++)
            scanf("%d", &W[i]);
        tree.init();
        for (int i = 0; i < n; i++) {
            A[i] = tree.newNode();
            A[i]->val = W[i];
        }
        for (int i = 1; i < n; i++) {
            scanf("%d %d", &x, &y);
            tree.link(A[x], A[y]);
        }
        scanf("%d", &m);
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d", &cmd, &x, &y);
            if (cmd == 1) {
                printf("%d\n", tree.gcdPath(A[x], A[y]));
            } else {
                tree.changeNode(A[x], y);
            }
        }
    }
    return 0;
}
/*
5
5 15 20 15 9
0 2
0 3
3 1
3 4
9999
1 2 1
1 1 3
2 3 3
1 1 4
1 1 3
*/