blog.chungzh.cn

题意

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)$？其实我不会算，但是挺快的。

#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 - 博客园

@ 2022/10/6 SM 模拟赛。