E. Xenia and Tree - 题解
比赛与标签
比赛: Codeforces Round 199 (Div. 2) 标签: data structures, divide and conquer, trees, *2400 难度: *2400
题目大意喵~
喵~ 主人 sama，欢迎来到 Xenia 的魔法树林！(ฅ'ω'ฅ)
在这个树林里，有一棵由 n 个节点组成的树。一开始，只有节点 1 是红色的，其他所有节点都是蓝色的。我们需要处理 m 个请求，请求有两种类型哦：
- 染色请求
1 v: 将指定的蓝色节点v染成红色。 - 查询请求
2 v: 找到离节点v最近的红色节点，并告诉本喵这个最短距离是多少。
距离的定义就是两个节点之间最短路径上的边数啦~ 我们的任务就是快速准确地完成这些请求的说！
平衡的艺术：根号分治大法！
主人你看，n 和 m 的规模都达到了 10^5，如果我们用太朴素的方法，肯定会超时的说！
- 朴素方法1: 每次查询时，都遍历一遍所有的红点，计算它们到目标点的距离，然后取最小值。如果红点越来越多，每次查询都会很慢很慢，喵呜~ (´;ω;`)
- 朴素方法2: 每次有节点被染红时，就立即从所有红点出发，做一次多源BFS，更新所有节点到最近红点的距离。这样查询是 O(1) 了，但染色一次就要 O(N) 的时间，更新太多次也受不了呀！
这两种方法都偏向了更新或查询的一方，不够均衡。所以，本喵想到了一个绝妙的主意——根号分治 (Square Root Decomposition)！这是一种平衡的艺术，让我们把问题变得优雅起来，喵~
核心思想是，我们不立即处理所有的更新，而是把它们“攒一攒”，攒到一定数量再批量处理！
我们将红点分为两类：
- “稳定”的红点：这些是已经被我们完全处理过的红点。我们用一个
dist数组来记录每个节点到最近的“稳定”红点的距离。 - “待处理”的红点：这些是新近被染红，但还没来得及对全局
dist数组做出贡献的红点。我们把它们暂时存放在一个叫buffer的小本本里。
有了这个设定，我们的操作就变成了这样：
查询操作 (类型 2)
当要查询节点 v 到最近红点的距离时，这个最近的红点要么是“稳定”的，要么是“待处理”的。所以，我们只需要：
- 先查一下
dist[v]，这是v到最近的“稳定”红点的距离。 - 再遍历一遍
buffer里所有“待处理”的红点u，计算v到每个u的距离。 - 最终的答案就是这两部分结果中的最小值！
ans = min(dist[v], min_{u ∈ buffer} {distance(u, v)})
那么，如何快速计算树上两点 u 和 v 的距离呢？当然是用 LCA (最近公共祖先) 啦！预处理之后，我们可以在 O(log N) 的时间内得到任意两点的距离，超快的说！distance(u, v) = depth[u] + depth[v] - 2 * depth[lca(u, v)]。
染色操作 (类型 1) 与 “大扫除” (Rebuild)
当一个节点 v 被染红时，我们先把它当作“待处理”的红点，扔进 buffer 小本本里。这个操作是 O(1) 的，非常快！
但是，如果 buffer 里的红点越攒越多，每次查询时遍历 buffer 的开销就会越来越大。为了防止查询变慢，我们需要定期进行“大扫除”！
我们设定一个阈值 block_size（通常取 sqrt(m) 或 sqrt(n) 效果比较好）。当 buffer 的大小达到这个阈值时，就触发一次“大扫除” (Rebuild) 操作：
- 将
buffer里的所有节点都“转正”，成为“稳定”的红点。 - 从
buffer里的所有节点同时出发，进行一次多源BFS (Multi-source BFS)。 - 在BFS的过程中，更新全局的
dist数组。对于树上任意节点x，dist[x] = min(dist[x], 新算出的距离)。 - 大扫除结束后，清空
buffer。所有红点又都变成了“稳定”状态，世界恢复了清爽！
通过这种方式，我们将大量的更新操作的计算成本分摊开来，实现了更新和查询之间美妙的平衡，喵~
Code 实现细节喵~
下面就是本喵写好的AC代码啦，附上了详细的注释，希望能帮到主人哦！
cpp
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <climits>
#include <algorithm>
using namespace std;
// LCA 结构体，用于快速计算树上两点距离
struct LCA {
int n, timer;
vector<vector<int>> G;
vector<int> enter, depth, exxit;
vector<pair<int, int>> linear;
vector<vector<pair<int, int>>> rmq;
const pair<int, int> INF = {INT_MAX, -1};
LCA(int n) : n(n), G(n), enter(n, -1), depth(n, 0), exxit(n, -1) {
timer = 0;
linear.resize(2 * n);
}
void add_edge(int u, int v) {
G[u].push_back(v);
G[v].push_back(u);
}
// DFS 遍历生成欧拉序
void dfs(int u, int dep) {
enter[u] = timer;
linear[timer] = {dep, u};
timer++;
depth[u] = dep;
for (int v : G[u]) {
if (enter[v] == -1) {
dfs(v, dep + 1);
linear[timer] = {dep, u};
timer++;
}
}
exxit[u] = timer;
}
// 构建 RMQ 表，用于O(1)查询区间最小值
void build(int root) {
dfs(root, 0);
int N = timer;
if (N == 0) return;
int logn = 0;
while ((1 << logn) < N) logn++;
if (logn == 0) logn = 1;
rmq.assign(logn, vector<pair<int, int>>(N));
for (int i = 0; i < N; i++) {
rmq[0][i] = linear[i];
}
for (int i = 1; i < logn; i++) {
int step = 1 << (i - 1);
for (int j = 0; j + (1 << i) <= N; j++) {
rmq[i][j] = min(rmq[i - 1][j], rmq[i - 1][j + step]);
}
}
}
// RMQ 查询
pair<int, int> query_rmq(int l, int r) {
if (l >= r) return INF;
int len = r - l;
int k = 31 - __builtin_clz(len); // 快速计算 log2(len)
return min(rmq[k][l], rmq[k][r - (1 << k)]);
}
// 查询 LCA
int lca(int u, int v) {
int a = enter[u], b = enter[v];
if (a > b) swap(a, b);
pair<int, int> p = query_rmq(a, b + 1);
return p.second;
}
// 计算两点距离
int dist(int u, int v) {
int w = lca(u, v);
return depth[u] + depth[v] - 2 * depth[w];
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<vector<int>> g(n);
LCA lca(n); // 初始化 LCA 结构体
// 建树
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
u--; v--;
g[u].push_back(v);
g[v].push_back(u);
lca.add_edge(u, v);
}
lca.build(0); // O(N log N) 预处理 LCA
// dist[i] 存储节点 i 到最近的“稳定”红点的距离
vector<int> dist(n, INT_MAX);
queue<int> q;
// 初始时，节点 1 (索引为0) 是红色的，进行一次BFS计算初始dist
dist[0] = 0;
q.push(0);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : g[u]) {
if (dist[v] > dist[u] + 1) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
// 根号分治的块大小
int block_size = (int)sqrt(m);
if (block_size == 0) block_size = 1;
// buffer 存放“待处理”的红点
vector<int> buffer;
for (int i = 0; i < m; i++) {
int type, v;
cin >> type >> v;
v--;
if (type == 1) { // 染色操作
buffer.push_back(v);
// 如果 buffer 满了，就进行“大扫除” (Rebuild)
if ((int)buffer.size() >= block_size) {
queue<int> q2; // 用于多源BFS的队列
for (int node : buffer) {
// 这些新红点到自己的距离是0
dist[node] = 0;
q2.push(node);
}
buffer.clear(); // 清空 buffer
// 多源BFS，更新全局 dist 数组
while (!q2.empty()) {
int u = q2.front(); q2.pop();
for (int neighbor : g[u]) {
if (dist[neighbor] > dist[u] + 1) {
dist[neighbor] = dist[u] + 1;
q2.push(neighbor);
}
}
}
}
} else { // 查询操作
// 1. 先获取到“稳定”红点的最短距离
int ans = dist[v];
// 2. 再和到“待处理”红点的最短距离比较
for (int u : buffer) {
int d = lca.dist(u, v);
if (d < ans)
ans = d;
}
cout << ans << '\n';
}
}
return 0;
}复杂度分析时间到！
时间复杂度: O(N log N + N * sqrt(M) + M * sqrt(M) * log N) 的说
- 预处理: LCA的构建需要 O(N log N) 的时间，初始的BFS需要 O(N) 的时间。
- 染色操作: 将节点加入
buffer是 O(1)。“大扫除”操作（多源BFS）每次需要 O(N) 时间。在m次查询中，最多会发生m / block_size次大扫除。如果block_size取sqrt(m)，这部分总时间是 O(m / sqrt(m) * N) = O(N * sqrt(m))。 - 查询操作: 每次查询，需要 O(1) 查
dist数组，然后遍历buffer。buffer的大小不会超过block_size。每次遍历计算距离需要 O(log N)。所以单次查询最坏是 O(block_size * log N)。m次查询总共是 O(m * block_size * log N)。如果block_size取sqrt(m)，这部分总时间是 O(m * sqrt(m) * log N)。 - 综合起来，总时间复杂度就是
O(N log N + N * sqrt(M) + M * sqrt(M) * log N)。虽然看起来有点吓人，但由于常数小和数据不极端，这个复杂度在5秒的时限内是可以通过的！
空间复杂度: O(N log N) 的说
- 主要是LCA中用于构建RMQ表的
rmq数组占用了 O(N log N) 的空间。其他如邻接表g、dist数组等都是 O(N) 的，buffer是 O(sqrt(M)) 的。所以瓶颈在LCA上。
- 主要是LCA中用于构建RMQ表的
知识点与总结
这道题真是一次有趣的冒险呢！它教会了我们几个非常重要的知识点：
- 根号分治 (Square Root Decomposition): 这是解决在线问题、平衡复杂度的强大思想！当遇到需要支持更新和查询，且两者操作朴素解法冲突时，可以考虑将更新（或查询）分块处理，达到一个更优的整体复杂度。
- LCA (最近公共祖先): 树上问题必备神器！通过欧拉序 + RMQ，可以 O(N log N) 预处理，O(1) 查询LCA，或者像本题代码一样 O(log N) 查询（因为
__builtin_clz不是严格O(1)）。有了LCA，计算距离、判断路径关系等都变得轻而易举。 - 多源BFS (Multi-source BFS): 当需要计算图中所有点到一个点集的最短距离时，多源BFS是标准解法。只需将所有源点初始距离设为0并加入队列，然后跑一次普通的BFS即可。
希望本喵的题解能帮助主人理解这个巧妙的解法！多练习这种平衡思想，就能像猫咪一样灵活地解决各种难题啦！加油喵！(๑•̀ㅂ•́)و✧