Zirnc's Blog

Recent content on Zirnc's Blog

马上订阅 Zirnc's Blog RSS 更新: https://blog.chungzh.cn/index.xml

CF-342E Xenia and Tree - 根号分治

2022年10月6日 08:00

CF342E Xenia and Tree

题意

给定一棵 $n$ 个节点的树，初始时 1 号节点为红色，其余为蓝色。

要求支持如下操作：

  1. 将一个节点变为红色。
  2. 询问节点 $u$ 到最近红色节点的距离。

共 $q$ 次操作。

$1 \le n, q \le 10 ^5$

分析

首先我们有两种暴力思路：

  1. 每次将一个点变为红色，就从那个点开始 BFS，更新它周边结点的最小值，直到无法更新。
  2. 每次询问，都和之前的红色点求 LCA，计算出距离，再取最小值。

这两种做法都过不了。但我们可以将它们结合起来，这就是根号分治（a.k.a. 操作分块）。

我们把操作序列以 $\sqrt m$ 为块长分块，对于一个询问，有两种情况：

  1. 在同一块内且在询问之前的修改，可以暴力 LCA 求距离。
  2. 对于之前块的修改，可以在处理完那个块之后，从块中修改的红点开始多源 BFS 更新每个点的答案。

最后答案便是两种情况取最小值。

大概也许是 $O((n+m)\sqrt m)$？其实我不会算，但是挺快的。

 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

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int LOGN = 17;
int n, m;
int f[MAXN][LOGN], depth[MAXN];
int tmpdis[MAXN];
vector<int> g[MAXN];
void dfs(int cur, int father...
剩余内容已隐藏
查看完整文章以阅读更多
查看完整文章