[blog.chungzh.cn](https://blog.chungzh.cn)
## 题意
[CF342E Xenia and Tree](https://www.luogu.com.cn/problem/CF342E)
给定一棵 $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)$？~~其实我不会算，但是挺快的~~。
```cpp
#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) {
depth[cur] = depth[father] +1;
f[cur][0] = father;
for (int i = 1; i < LOGN; i++)
f[cur][i] = f[f[cur][i-1]][i-1];
for (int i = 0; i < g[cur].size(); i++) {
if (g[cur][i] == father) continue;
dfs(g[cur][i], cur);
}
}
int lca(int u, int v) {
if (depth[u] > depth[v]) swap(u, v);
for (int i = LOGN-1; i >= 0; i--) {
if (depth[f[v][i]] >= depth[u]) v = f[v][i];
}
for (int i = LOGN-1; i >= 0; i--) {
int s = f[u][i], t = f[v][i];
if (s != t) {
u = s;
v = t;
}
}
if (u != v)
return f[u][0];
return u;
}
int dist(int u, int v) {
int l = lca(u, v);
return depth[u]+depth[v] - 2*depth[l];
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n-1; i++) {
int u, v;
scanf("%d%d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1, 1);
int b = sqrt(m);
vector<int> buf;
memset(tmpdis, 0x3f, sizeof tmpdis);
buf.push_back(1);
for (int i = 0; i < m; i++) {
int type, v;
scanf("%d%d", &type, &v);
if (type == 1) {
buf.push_back(v);
} else {
// 之前块的答案记在 tmpdis 中
int ans = tmpdis[v];
for (int i = 0; i < buf.size(); i++)
ans = min(ans, dist(v, buf[i])); // 当前块直接暴力 LCA
printf("%d\n", ans);
}
if (i%b == 0) {
queue<int> q;
for (int i = 0; i < buf.size(); i++) {
q.push(buf[i]);
tmpdis[buf[i]] = 0;
}
buf.clear();
// BFS 记录答案
while (!q.empty()) {
int f = q.front();
q.pop();
for (int i = 0; i < g[f].size(); i++) {
if (tmpdis[g[f][i]] > tmpdis[f]+1) {
tmpdis[g[f][i]] = tmpdis[f]+1;
q.push(g[f][i]);
}
}
}
}
}
return 0;
}
```
参考：[[CF342E] Xenia and Tree - 分块,ST表,LCA - Mollnn - 博客园](https://www.cnblogs.com/mollnn/p/14321397.html)
------
> @ 2022/10/6 SM 模拟赛。