题目描述
不久之前，Mirko建立了一个旅行社，名叫“极地之梦”。这家旅行社在北极附近购买了N座冰岛，并且提供观光服
务。当地最受欢迎的当然是帝企鹅了，这些小家伙经常成群结队的游走在各个冰岛之间。Mirko的旅行社遭受一次
重大打击，以至于观光游轮已经不划算了。旅行社将在冰岛之间建造大桥，并用观光巴士来运载游客。Mirko希望
开发一个电脑程序来管理这些大桥的建造过程，以免有不可预料的错误发生。这些冰岛从1到N标号。一开始时这些
岛屿没有大桥连接，并且所有岛上的帝企鹅数量都是知道的。每座岛上的企鹅数量虽然会有所改变，但是始终在[0
, 1000]之间。你的程序需要处理以下三种命令：
1.”bridge A B”——在A与B之间建立一座大桥（A与B是不同的岛屿）。由于经费限制，这项命令被接受，当且仅当
A与B不联通。若这项命令被接受，你的程序需要输出”yes”，之
后会建造这座大桥。否则，你的程序需要输出”no”。
2.”penguins A X”——根据可靠消息，岛屿A此时的帝企鹅数量变为X。这项命令只是用来提供信息的，你的程序不
需要回应。
3.”excursion A B”——一个旅行团希望从A出发到B。若A与B连通，你的程序需要输出这个旅行团一路上所能看到的
帝企鹅数量（包括起点A与终点B），若不联通，你的程序需要输出”impossible”。
输入格式
第一行一个正整数N，表示冰岛的数量。
第二行N个范围[0, 1000]的整数，为每座岛屿初始的帝企鹅数量。
第三行一个正整数M，表示命令的数量。接下来M行即命令，为题目描述所示。
1<=N<=30000,1<=M<=100000
输出格式
对于每个bridge命令与excursion命令，输出一行，为题目描述所示。
输入样例
5
4 2 4 5 6
10
excursion 1 1
excursion 1 2
bridge 1 2
excursion 1 2
bridge 3 4
bridge 3 5
excursion 4 5
bridge 1 3
excursion 2 4
excursion 2 5
输出样例
impossible
yes
6
yes
yes
15
yes
15
16
Solution
最近刚学了一个Link-Cut Tree，于是找了几个题练习。
这道题是道LCT裸题，就是修改操作有些麻烦，需要splay一下在修改。
Code
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
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define ls(x) c[x][0]
#define rs(x) c[x][1]
#define MAXN 100010
int si[MAXN], val[MAXN], st[MAXN], c[MAXN][2], f[MAXN];
bool r[MAXN];
int n, m, u, v;
char op[10];
bool ifr(int p) {
return ls(f[p]) == p || rs(f[p]) == p;
}
void pd(int p) {
si[p] = si[ls(p)] + si[rs(p)] + val[p];
}
void flit(int p) {
int t = ls(p);
ls(p) = rs(p);
rs(p) = t;
r[p] ^= 1;
}
void pushd(int p) {
if (r[p]) {
if (ls(p)) flit(ls(p));
if (rs(p)) flit(rs(p));
r[p] = 0;
}
}
void rotate(int p) {
int x = f[p], y = f[x], k = rs(x) == p, w = c[p][!k];
if (ifr(x)) c[y][c[y][1] == x] = p;
c[p][!k] = x;
c[x][k] = w;
if (w) f[w] = x;
f[x] = p;
f[p] = y;
pd(x);
}
void splay(int p) {
int y = p, z = 0;
st[++z] = y;
while (ifr(y)) st[++z] = y = f[y];
while (z) pushd(st[z--]);
while (ifr(p)) {
y = f[p];
z = f[y];
if (ifr(y)) {
rotate((ls(y) == p) ^ (ls(z) == y) ? p : y);
}
rotate(p);
}
pd(p);
}
void access(int p) {
for (int i = 0; p; p = f[i = p]) {
splay(p);
rs(p) = i;
pd(p);
}
}
void makeroot(int p) {
access(p);
splay(p);
flit(p);
}
int findr(int p) {
access(p);
splay(p);
while (ls(p)) {
pushd(p);
p = ls(p);
}
splay(p);
return p;
}
void split(int x, int y) {
makeroot(x);
access(y);
splay(y);
}
bool link(int x, int y) {
makeroot(x);
if (findr(y) != x) {
f[x] = y;
return 1;
}
return 0;
}
void cut(int x, int y) {
makeroot(x);
if (findr(y) == x && f[y] == x && !ls(y)) {
f[y] = rs(x) = 0;
pd(x);
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &val[i]);
}
scanf("%d", &m);
while (m--) {
scanf("%s%d%d", op, &u, &v);
if (op[0] == 'b') {
if (link(u, v)) {
puts("yes");
}
else {
puts("no");
}
}
if (op[0] == 'p') {
splay(u);
val[u] = v;
pd(u);
}
if (op[0] == 'e') {
if (findr(u) == findr(v)) {
split(u, v);
printf("%d\n", si[v]);
}
else {
puts("impossible");
}
}
}
}
|
