目录

  1. 引言
  2. BZOJ 3779: 重组病毒
    1. Description
    2. Input
    3. Output
    4. Sample Input
    5. Sample Output
    6. HINT
    7. 题目分析
    8. 代码

引言

BZOJ 3779: 重组病毒 题解

BZOJ 3779: 重组病毒

  • Time Limit: 20 Sec

  • Memory Limit: 512 MB

Description

黑客们通过对已有的病毒反编译,将许多不同的病毒重组,并重新编译出了新型的重组病毒。这种病毒的繁殖和变异能力极强。为了阻止这种病毒传播,某安全机构策划了一次实验,来研究这种病毒。
实验在一个封闭的局域网内进行。局域网内有n台计算机,编号为1~n。一些计算机之间通过网线直接相连,形成树形的结构。局域网中有一台特殊的计算机,称之为核心计算机。根据一些初步的研究,研究员们拟定了一个一共m步的实验。实验开始之前,核心计算机的编号为1,每台计算机中都有病毒的一个变种,而且每台计算机中的变种都不相同。实验中的每一步会是下面中的一种操作:
1、 RELEASE x
在编号为x的计算机中植入病毒的一个新变种。这个变种在植入之前不存在于局域网中。
2、 RECENTER x
将核心计算机改为编号为x的计算机。但是这个操作会导致原来核心计算机中的病毒产生新变种,并感染过来。换言之,假设操作前的核心计算机编号为y,相当于在操作后附加了一次RELEASE y的操作。
根据研究的结论,在植入一个新变种时,病毒会在局域网中搜索核心计算机的位置,并沿着网络中最短的路径感染过去。
而第一轮实验揭露了一个惊人的真相:病毒的不同变种是互斥的。新变种在感染一台已经被旧变种感染的电脑时,会把旧变种完全销毁之后再感染。但研究员发现了实现过程中的漏洞。如果新变种在感染过程中尚未销毁过这类旧变种,需要先花费1单位时间分析旧变种,才能销毁。如果之前销毁过这类旧变种,就可以认为销毁不花费时间。病毒在两台计算机之间的传播亦可认为不花费时间。
研究员对整个感染过程的耗时特别感兴趣,因为这是消灭病毒的最好时机。于是在m步实验之中,研究员有时还会做出如下的询问:
3、 REQUEST x
询问如果在编号为x的计算机的关键集合中的计算机中植入一个新变种,平均感染时间为多长。编号为y的计算机在编号为x的计算机的关键集合中,当且仅当从y沿网络中的最短路径感染到核心计算机必须经过x。由于有RECENTER操作的存在,这个集合并不一定是始终不变的。
至此,安全机构认为已经不需要实际的实验了,于是他们拜托你编写一个程序,模拟实验的结果,并回答所有的询问。

Input

输入的第一行包含两个整数n和m,分别代表局域网中计算机的数量,以及操作和询问的总数。
接下来n-1行,每行包含两个整数x和y,表示局域网中编号为x和y的计算机之间有网线直接相连。
接下来m行,每行包含一个操作或者询问,格式如问题描述中所述。

Output

对于每个询问,输出一个实数,代表平均感染时间。输出与答案的绝对误差不超过 10^(-6)时才会被视为正确。

Sample Input

8 6

1 2

1 3

2 8

3 4

3 5

3 6

4 7

REQUEST 7

RELEASE 3

REQUEST 3

RECENTER 5

RELEASE 2

REQUEST 1

Sample Output

4.0000000000

2.0000000000

1.3333333333

HINT

N < = 1 00 000 M < = 1 00 000

题目分析

这道题其实和SDOI2017的树点涂色那道题很像的,只不过多了一个换根操作,实际难度就大幅提升……

首先,我们知道第一种操作可以类比LCT中的access,所以,我们可以用LCT的树剖分来维护每种颜色的情况,也即,在一条重链里的所有点的颜色是相同的

那么,我们就需要分析题目所求的东西是什么,我们经过分析可以发现,一个点感染到根的时间就等于这个点到根的轻边树加一,那么,我们只需要维护一个点到根经过了多少条轻边就可以了

联想边的轻重转换,我们知道,一条边的转换,只有可能发生于access操作中,我们还知道,树上信息的维护可以使用DFS序+线段树,因为它支持快速方便的子树修改,如果还有链修改,那么就可以使用树链剖分+线段树,由于access不会涉及链修改,所以也不需要这样做

我们不妨从$1$开始遍历,求出DFS序

具体方法就是我们在每次access切换边的轻重的时候,在这条边下面的子树中进行子树修改,即区间加一或减一,当然,这是正常的情况,由于本题支持换根,所以当一个点$x$为根时,从$x$到$1$的路径上的所有点的子树方向会发生改变(其实不够准确,因为有些子树仍是它的子树,但是请体会精神……),我们需要考虑这样的情况,更特殊的,当当前点为根的时候,我们需要对整个区间进行操作,而这些如果不特殊判断都是会有问题的

如何讨论情况呢,下面分条阐述:

  • 当前点为根,直接维护一下当前的根是什么就可以了,直接关于整个区间操作

  • 当前点在$1$到根的链上,我们可以用根的DFS序和这个点的DFS序进行比较,看看这个点的是否包含根的,如果是,那么就在链上,否则不在,在此时的父亲的区间补集(最多两个区间)上操作即可

  • 剩下就是正常情况直接搞就可以了,在关于这个点占据的DFS区间上操作即可

那么只剩下一个问题了,就是如何寻找当前树上的父亲,我们需要先把当前点旋到根,然后有两种情况:

  • 当前点有左儿子,那么这个点不是链的顶端,找这条链上的它的前驱即可,注意为了保证时间复杂度,找到了以后要Splay它一下

  • 当前点没有左儿子,这个点是链的顶端,直接返回它的父亲即可

那么,问题就都解决了

代码

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
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cassert>
#define maxn 400005
#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), 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 == '-') ch = gc(), f = 0;
while ('0' <= ch && ch <= '9') x = (x << 1) + (x << 3) + ch - '0', ch = gc();
if (!f) x = -x;
}
int n, m;
namespace Tree_Chain_Partition{
#define erep(i, x) for (register int i = h[x]; i; i = e[i].next)
const int root = 1;
struct edge{
int next, to;
edge(int next = 0, int to = 0) : next(next), to(to){}
}e[maxn << 1];
int h[maxn], cnt = 1;
inline void Add_Edge(int& x, int& y){
e[++cnt] = edge(h[x], y);
h[x] = cnt;
e[++cnt] = edge(h[y], x);
h[y] = cnt;
}
int fa[maxn];
int siz[maxn];
int son[maxn];
int dfs[maxn];
int idfs[maxn];
int top[maxn];
int d[maxn];
int t = 0;
void DFS(int x){
siz[x] = 1;
erep(i, x){
int op = e[i].to;
if (op == fa[x]) continue;
fa[op] = x;
d[op] = d[x] + 1;
DFS(op);
siz[x] += siz[op];
if (siz[op] > siz[son[x]]) son[x] = op;
}
}
void DFS(int x, int tp){
dfs[x] = ++t;
idfs[t] = x;
top[x] = tp;
if (son[x]) DFS(son[x], tp);
erep(i, x){
int op = e[i].to;
if (op == fa[x] || op == son[x]) continue;
DFS(op, op);
}
}
ll sum[maxn << 1];
int add[maxn << 1];
int qx, qy, qd;
inline void pushup(int& o){
sum[o] = sum[o << 1] + sum[o << 1 | 1];
}
inline void pushdown(int& l, int& r, int& o){
if (add[o] && l != r){
int x = add[o];
int mid = ((r - l) >> 1) + l;
add[o << 1] += x, add[o << 1 | 1] += x;
sum[o << 1] += (ll)(mid - l + 1) * x;
sum[o << 1 | 1] += (ll)(r - mid) * x;
add[o] = 0;
}
}
void init(int l, int r, int o){
if (l == r){
sum[o] = d[idfs[l]] + 1;
return;
}
int mid = ((r - l) >> 1) + l;
init(l, mid, o << 1);
init(mid + 1, r, o << 1 | 1);
pushup(o);
}
void Add(int l, int r, int o){
pushdown(l, r, o);
if (qx <= l && r <= qy){
add[o] += qd;
sum[o] += (ll)(r - l + 1) * qd;
return;
}
int mid = ((r - l) >> 1) + l;
if (qx <= mid) Add(l, mid, o << 1);
if (qy > mid) Add(mid + 1, r, o << 1 | 1);
pushup(o);
}
ll get_sum(int l, int r, int o){
pushdown(l, r, o);
if (qx <= l && r <= qy) return sum[o];
int mid = ((r - l) >> 1) + l;
ll ans = 0;
if (qx <= mid) ans += get_sum(l, mid, o << 1);
if (qy > mid) ans += get_sum(mid + 1, r, o << 1 | 1);
return ans;
}
void init(){
DFS(1);
DFS(1, 1);
init(1, n, 1);
}
}
using Tree_Chain_Partition :: init;
using Tree_Chain_Partition :: get_sum;
using Tree_Chain_Partition :: Add;
using Tree_Chain_Partition :: dfs;
using Tree_Chain_Partition :: siz;
using Tree_Chain_Partition :: qx;
using Tree_Chain_Partition :: qy;
using Tree_Chain_Partition :: qd;
using Tree_Chain_Partition :: Add_Edge;
namespace Link_Cut_Tree{
#define ls ch[x][0]
#define rs ch[x][1]
int root;
int ch[maxn][2];
int fa[maxn];
bool rev[maxn];
inline bool is_root(int& x){
return ch[fa[x]][0] != x && ch[fa[x]][1] != x;
}
inline void pushdown(int x){
if (rev[x]){
rev[ls] ^= 1, rev[rs] ^= 1;
swap(ls, rs);
rev[x] = 0;
}
}
inline void rotate(int x){
int k = x;
x = fa[x];
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;
}
int st[maxn];
int cst = 0;
void splay(int x){
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 ((ch[f1][1] == x) ^ (ch[f2][1] == f1)) rotate(x);
else rotate(f1);
}
rotate(x);
}
}
inline bool judge(int x){//1 正序,0 逆序
if (dfs[x] <= dfs[root] && dfs[root] + siz[root] - 1 <= dfs[x] + siz[x] - 1) return 0;
return 1;
}
void Modify(int x, int op){
if (x == root) qx = 1, qy = n, qd = op, Add(1, n, 1);
else if (judge(x)) qx = dfs[x], qy = dfs[x] + siz[x] - 1, qd = op, Add(1, n, 1);
else{
qx = 1, qy = n, qd = op, Add(1, n, 1);
x = fa[x];
qx = dfs[x], qy = dfs[x] + siz[x] - 1, qd = -op, Add(1, n, 1);
}
}
void access(int x){
int t = 0;
while (x){
splay(x);
int k = rs;
if (t) {
while (pushdown(t), ch[t][0]) t = ch[t][0];
splay(t);
Modify(t, -1);
}
rs = t;
if (k) {
while (pushdown(k), ch[k][0]) k = ch[k][0];
splay(k);
Modify(k, 1);
}
t = x;
x = fa[x];
}
}
void moveroot(int x){
access(x);
splay(x);
root = x;
rev[x] ^= 1;
}
void get_ans(int x){
if (x == root) qx = 1, qy = n, printf("%.10lf\n", (double)1.0 * get_sum(1, n, 1) / n);
else if (judge(x)) qx = dfs[x], qy = dfs[x] + siz[x] - 1, printf("%.10lf\n", (double)1.0 * get_sum(1, n, 1) / siz[x]);
else{
splay(x);
qx = 1, qy = n;
ll a = get_sum(1, n, 1), b = n;
if (ls){
x = ls;
while (pushdown(x), rs) x = rs;
}
else if (fa[x]) x = fa[x];
qx = dfs[x], qy = dfs[x] + siz[x] - 1, a -= get_sum(1, n, 1), b -= siz[x];
printf("%.10lf\n", (double)1.0 * a / b);
}
}
}
using Link_Cut_Tree :: access;
using Link_Cut_Tree :: moveroot;
using Link_Cut_Tree :: get_ans;
void Release(int& x){
access(x);
}
void Recenter(int& x){
moveroot(x);
}
void Request(int& x){
get_ans(x);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("virus.in", "r", stdin);
#endif
int x, y;
read(n), read(m);
rep(i, 1, n - 1) read(x), read(y), Add_Edge(x, y);
init();
rep(i, 1, n) Link_Cut_Tree :: fa[i] = Tree_Chain_Partition :: fa[i];
Link_Cut_Tree :: root = 1;
rep(i, 1, m){
char op = gc();
while (op != 'Q' && op != 'L' && op != 'C') op = gc();
switch(op){
case 'L': read(x), Release(x); break;
case 'C': read(x), Recenter(x); break;
case 'Q': read(x), Request(x); break;
default: break;
}
}
return 0;
}

然而我还是非常SB的用了树链剖分……