目录

  1. 引言
  2. BZOJ 3510: 首都
    1. Description
    2. Input
    3. Output
    4. Sample Input
    5. Sample Output
    6. HINT
    7. 题目分析
    8. 代码

引言

BZOJ 3510: 首都 题解

BZOJ 3510: 首都

  • Time Limit: 10 Sec

  • Memory Limit: 256 MB

Description

在X星球上有N个国家,每个国家占据着X星球的一座城市。由于国家之间是敌对关系,所以不同国家的两个城市是不会有公路相连的。
X星球上战乱频发,如果A国打败了B国,那么B国将永远从这个星球消失,而B国的国土也将归A国管辖。A国国王为了加强统治,会在A国和B国之间修建一条公路,即选择原A国的某个城市和B国某个城市,修建一条连接这两座城市的公路。
同样为了便于统治自己的国家,国家的首都会选在某个使得其他城市到它距离之和最小的城市,这里的距离是指需要经过公路的条数,如果有多个这样的城市,编号最小的将成为首都。
现在告诉你发生在X星球的战事,需要你处理一些关于国家首都的信息,具体地,有如下3种信息需要处理:
1、A x y:表示某两个国家发生战乱,战胜国选择了x城市和y城市,在它们之间修建公路(保证其中城市一个在战胜国另一个在战败国)。
2、Q x:询问当前编号为x的城市所在国家的首都。
3、Xor:询问当前所有国家首都编号的异或和。

Input

第一行是整数N,M,表示城市数和需要处理的信息数。
接下来每行是一个信息,格式如题目描述(A、Q、Xor中的某一种)。

Output

输出包含若干行,为处理Q和Xor信息的结果。

Sample Input

10 10

Xor

Q 1

A 10 1

A 1 4

Q 4

Q 10

A 7 6

Xor

Q 7

Xor

Sample Output

11

1

1

1

2

6

2

HINT

对于100%的数据,2<=N<=100000,1<=M<=200000。

题目分析

首先这题要我们寻找树的重心,这个是挺有意思的,因为我们知道重心的性质是非常多的,于是我猜想了一个性质,两棵树合并后,重心一定在原来两棵树的重心的路径上

其实也挺显然的,想想重心的递归求法,再结合一下定义就明白了

但是,我们发现,即便如此,我们无法精确地直接求出中心位置(也许可以二分??不知道),所以,我们可以考虑暴力地移动重心,但是,路径长度是$O(n)$的,这样做时间复杂度无法保证,怎么办呢?

我们继续研究,发现,中心移动的距离不会超过这两棵树的大小,这非常显然,所以,基于这个思路,我们可以尝试启发式合并,把小树链到大树上然后移动大树的重心,这样,大树移动的步数不会超过$O(小树大小)$,这便是启发式合并了,复杂度$O(nlog ^ 2 n)$

那么我们要做的,就是用并查集维护每棵树的大小和重心,然后合并以及移动重心

看网上题解都是把点一个一个插入,感觉好傻哦,为什么不直接链到上面然后再移动重心呢?所以,我们先把小树链上去,然后split一下两个重心,然后在这个Splay上不断地找后继,这便是移动重心了

但是,移动需要用到子树大小,我们怎么维护呢?我们知道,在LCT上是可以维护子树大小的,我们可以多记录一个虚子树大小的信息,那么在一个点执行access操作以后,这个点的虚子树大小加一就是原树上的它的子树的大小,但是,在移动中心的时候,我们也不能每次都调用一下access对吧,这样复杂度无法保证,但是我们知道,当前点的下一个点的子树大小,其实就是Splay上这个点的右子树的大小,这个大小包含了所有下面的所有点的实子树加虚子树大小

这样,我们就可以根据这个信息来移动重心了,因为根据前面的性质,我们只需要判断这棵子树大小与整块大小的一半的关系,注意,当存在两个重心时,需要特殊地处理一下

细节其实也挺TM多的……

代码

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
182
183
184
185
186
187
188
189
190
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cassert>
//#define DEBUG
#define maxn 200005
#define INF 2000000005
#define ls ch[x][0]
#define rs ch[x][1]
#define ll long long int
#define rep(i, l, r) for (register int i = l; i <= r; i++)
#define per(i, r, l) for (register int i = r; i >= l; i--)
#define gc() ((p1 == p2 && (p2 = (p1 = buffer) + fread(buffer, 1, maxn, stdin), p1 == p2)) ? EOF : *p1++)
using namespace std;
char *p1, *p2;
char buffer[maxn];
template <class T> void read(T& x){
char ch = gc(); x = 0; bool f = 1;
while (!('0' <= ch && ch <= '9') && ch != '-') ch = gc();
if (ch == '-') f = 0, ch = gc();
while ('0' <= ch && ch <= '9') x = (x << 1) + (x << 3) + ch - '0', ch = gc();
if (!f) x = -x;
}
int n, m;
int xorsum = 0;
int g[maxn];
int ufs[maxn];
int sum[maxn];//树的大小
int find_root(int x){
return ufs[x] = (x == ufs[x]) ? x : find_root(ufs[x]);
}
int ch[maxn][2];
int fa[maxn];
int vsiz[maxn], siz[maxn];
bool rev[maxn];
void debug(int x){
printf("第%d次操作, 要输出的可真是多啊.....\n", x);
rep(i, 1, n) {
int k = find_root(i);
if (k == i) printf("#%d : ufs = %d, sum = %d, g = %d\n", i, ufs[i], sum[i], g[i]);
else printf("#%d : ufs = %d\n", i, ufs[i]);
}
rep(i, 1, n){
printf("#%d : siz = %d, vsiz = %d, fa = %d, rev = %d, ls = %d, rs = %d\n", i, siz[i], vsiz[i], fa[i], rev[i], ch[i][0], ch[i][1]);
}
printf("\n\n\n");
}
inline bool is_root(int x){
return ch[fa[x]][0] != x && ch[fa[x]][1] != x;
}
inline void pushup(int x){
siz[x] = siz[ls] + siz[rs] + vsiz[x] + 1;
}
inline void pushv(int x, int op){ //op == 1 || op == -1
vsiz[fa[x]] += op * siz[x];
}
inline void pushdown(int x){
if (rev[x]){
rev[ls] ^= 1, rev[rs] ^= 1;
rev[x] = 0;
swap(ls, rs);
}
}
inline void rotate(int x){
int k = x;
x = fa[x];
if (!x) return;
fa[k] = fa[x];
int d = ch[x][1] == k;
if (!is_root(x)) ch[fa[x]][ch[fa[x]][1] == x] = k;
ch[x][d] = ch[k][d ^ 1];
fa[ch[x][d]] = x;
ch[k][d ^ 1] = x;
fa[x] = k;
pushup(x);
pushup(k);
}
int st[maxn];
int cst = 0;
void splay(int x){
if (!x) assert(false);
int t = x;
while (!is_root(x)){
st[++cst] = x;
x = fa[x];
}
st[++cst] = x;
while (cst){
pushdown(st[cst]);
cst--;
}
x = t;
while (!is_root(x)){
int f1 = fa[x];
if (!is_root(f1)){
int f2 = fa[f1];
if (!x) assert(false);
if ((ch[f1][1] == x) ^ (ch[f2][1] == f1)) rotate(x);
else rotate(f1);
}
if (!x) assert(false);
rotate(x);
}
}
void access(int x){
int t = 0;
while (x){
splay(x);
pushv(rs, 1), pushv(t, -1);//Warning!!!
rs = t;
pushup(x);
t = x;
x = fa[x];
}
}
void moveroot(int x){
access(x);
splay(x);
rev[x] ^= 1;
}
void merge(int x, int y){
int _x = find_root(x), _y = find_root(y);
if (sum[_x] > sum[_y]) swap(_x, _y), swap(x, y);//Error!!!!!
sum[_y] += sum[_x];
ufs[_x] = _y;
xorsum ^= g[_x] ^ g[_y];
access(y), splay(y);//Error!!!
moveroot(x);
fa[x] = y;
pushv(x, 1);
moveroot(g[_y]);
access(g[_x]);
splay(g[_y]);
x = g[_y]; int con = sum[_y] >> 1;
g[_y] = INF;//Warning!!!
while (1){
pushdown(x);
int subtree_siz = siz[rs];
if (subtree_siz < con) break;
else if (subtree_siz == con){
if (sum[_y] & 1) break;
else g[_y] = x;
}
x = rs;
while (pushdown(x), ls) x = ls;//Error!!!!!!!!!
splay(x);
}
g[_y] = min(g[_y], x);
xorsum ^= g[_y];
}
int main(){
#ifndef ONLINE_JUDGE
freopen("capital.in", "r", stdin);
#endif
int x, y;
read(n), read(m);
rep(i, 1, n) ufs[i] = i, g[i] = i, sum[i] = 1, xorsum ^= i;
rep(i, 1, m){
char op = gc();
while (op != 'A' && op != 'X' && op != 'Q') op = gc();
switch(op){
case 'A': read(x), read(y), merge(x, y); break;
case 'Q': read(x), printf("%d\n", g[find_root(x)]); break;
case 'X': printf("%d\n", xorsum); break;
}
#ifdef DEBUG
debug(i);
#endif
}
return 0;
}

关于代码的细节及坑点可以观察上面的Warning和Error