企业官网建设流程全解析

某次联考Day2，我打开 “JZOJ3875” 的题目列表，看到第一题叫“星球联盟（alliance）”，脚本后缀写着(Standard IO)。常年刷OJ的人都知道，Standard IO 意味着评测走标准输入输出，别自作聪明写freopen。这类题名字听起来很科幻——星际航行、星球外交、联盟扩张，但剥掉包装之后，它几乎就是一道标准图论题：动态加边、按时间回答连通性问题。我当时扫完题面第一反应是“可以套并查集”，但再看了一眼询问方式，发现事情没那么简单。

网上很多题解会把这道题讲得云里雾里，又是“联盟势力”又是“扩张顺序”。我习惯先把背景全扔掉，只留下最核心的模型。这篇博文就按我自己的推导过程来写，从题意翻译、暴力复杂度分析，到关键解法“时间生成森林 + 倍增路径最大值”，再到我实际写代码时踩过的坑。如果你正要参加NOIP级别的比赛，或者正在刷八校联考历史题，那这篇内容应该能帮你少走不少弯路。

1. 第一次读题时我看到了什么：题意拆解与模型建立

1.1 题目背景的翻译过程

“星球联盟”的故事背景大概是：宇宙里有 N 个星球，一开始各自独立，每个星球都只属于自己那个“光杆联盟”。随着时间推移，不同星球之间会建立双向的航道，航道一旦建好就一直存在。后面给出若干次询问，每次问两个星球 u、v：从第几条航道建立之后，这两个星球开始属于同一个联盟。

如果你做过一点图论题，立刻能看出这里每个星球就是一个节点，每条航道就是一条无向边，“属于同一个联盟”就是两个节点在同一个连通块里。于是这个题就变成：

按时间顺序依次加入 M 条无向边，有 K 次询问，每次给定两个点 u、v，要求输出它们最早在第几条边加入后连通，如果始终不连通则输出 -1。

这种“动态加边 + 连通性 + 时间戳”的组合，正是 NOIP 级别考试特别喜欢出的方向。它不会直接考你“当前是否连通”这种一眼并查集的题，而是加了一个“最早何时”的维度，让问题从静态变成了带时间轴的结构。

我拿到的题目数据范围大概是 N、M、K 都在 2e5 级别，这意味着单次询问跑全图、或者每个询问都二分重建并查集，基本都会超时。你在自己做题时如果发现数据规模不同，算法骨架通常仍然适用，只是常数和预处理细节可能需要微调。

1.2 前置知识与目标复杂度

在做这道题之前，最好确保自己已经熟练这几个工具：路径压缩并查集、DFS 遍历森林、倍增求 LCA。这三样东西在初赛复赛里都属于必备技能，如果哪个还不熟，建议先找板子题各刷两三道再回来。不然你可能会被后面的“生成森林 + 最大值 LCA”卡在预处理环节，而不是卡在算法理解上。

我的目标复杂度很明确：建树阶段 O(M α(N))，预处理阶段 O(N log N)，每个询问 O(log N) 回答。也就是总体 O((M + N + K) log N) 级别，这个复杂度在 2e5 的数据下能够非常稳定地通过。至于为什么是“生成森林 + LCA”，而不是更简单的在线并查集，下面慢慢拆。

2. 为什么暴力做法的每一步都踩在时间爆炸的边缘

2.1 两种朴素方案的复杂度算账

刚读完题，很多人第一反应是“直接模拟”。对于询问 (u, v)，从第 1 条边开始枚举，每加入一条边就用并查集连接两个端点，一旦发现 u 和 v 连通就输出当前边的编号。这个思路对不对？结论是对的，但复杂度完全不可接受：一个询问最坏要扫完 M 条边，K 个询问就是 O(KM)。当 K 和 M 都到 2e5 时，运算量是 4e10 级别，瓶颈瓶颈再瓶颈。这就是我在草稿纸上算完第一遍之后直接划掉的做法。

也有人会想到“二分答案时刻”。每个询问二分一个边编号 mid，把 1 到 mid 的边全部加入并查集，检查 u、v 是否连通。复杂度是 O(K log M (N+M)) 左右，仍然是上亿次并查集操作，而且每轮二分都要重新初始化并查集数组，常数非常大。更关键的是，这种做法还没触及题目的核心——题目要的是“首次连通的时间”，不是“在某个给定时刻是否连通”，所以就算你把所有询问按时间排序、把边一条条加进去，也没法直接回答“首次”。

2.2 关键突破口：把时间戳变成树边权

我在草稿纸上画了一个小例子：假设有 1、2、3 三个点，边 (1, 2) 在第 5 轮加入，边 (2, 3) 在第 9 轮加入。那么 1 和 3 从第 9 轮开始连通。这时我盯着“第 9 轮”这个数字想：它恰好是路径 1-2-3 上所有边的时间戳最大值。

这个观察很微妙但非常关键。如果两点的路径上有一条边还没出现，那么整条路径就断了，两点不可能连通；只有当路径上每一条边都已经出现时，路径才成立。由于边是按全局时间顺序出现的，所以路径上最大的那个时间戳，就是整条路径“刚刚成立”的那一刻。

顺着这个思路想下去：如果我把所有边按时间顺序处理，只保留那些“让两个不同连通块合并”的边，丢掉所有“加在当前连通块内部”的边，那么保留下来的边会构成一个森林。这个森林里每条边都带有一个时间权值，任意两点之间若有路径，路径上所有边权值的最大值就是它们最早连通的时刻。于是整道题从“动态加边 + 时间询问”变成了“静态树上路径最大值查询”，后者的标准做法就是倍增 LCA。这就是我这道题真正的突破口。

3. 核心解法：时间生成森林 + 倍增路径最大值

3.1 只保留“促成连通”的边，为什么不会丢答案

具体操作分两步。第一步，顺序读入 M 条边，每读一条边 (u, v)，就用并查集判断当前 u、v 是否已经连通：如果不连通，说明这是一条“合并边”，把它加入我们准备建的森林，同时给这条边打上“当前轮次”的时间戳，再在并查集里把 u、v 合并；如果已经连通，说明它是“冗余边”，直接丢弃。第二步，用建好的森林回答所有 K 次询问。

有人会担心：丢掉的那些边里，是不是可能存在一条“捷径”，让某两个点的首次连通时间变得更早？答案是不会。因为如果我们把原始动态图在某个时刻的前缀边全部拿出来，和这个时刻已经加入的树边放在一起比较，两者的连通块划分是完全一致的。这个性质可以用数学归纳法证明：初始时都是孤立点；每读入一条新边时，原始图里发生一次连通块合并，树边也恰好保存了这次合并，两者同步变化。那些被丢弃的边永远只连接同一个连通块内的两个点，不改变任何连通性信息。

所以说，生成森林在“连通性何时建立”这个问题上，是原始动态图的完美压缩表示。两点在原始动态图中最终是否连通，完全等价于它们在生成森林中是否连通；而它们最早连通的时刻，就是它们在生成森林唯一路径上的最大边权。

3.2 从“判断是否连通”到“路径最大值”的整套流程

接下来的工作就非常套路了。先处理森林的 DFS 初始化：由于原始图不一定连通，我们需要从每个还没有被访问过的点开始 DFS，遍历整个连通块，同时记录每个节点的深度dep[x]、向上 2^j 步的祖先f[j][x]、以及向上跳这 2^j 步过程中经过边权的最大值mx[j][x]。

回答查询 (u, v) 时，先用建树结束后的最终并查集判断find(u)和find(v)是否相等：如果不相等，直接输出 -1；如果相等，说明它们一定在生成森林的同一棵树上。此时就在树里做标准 LCA，但把“找祖先”的过程顺便改成“统计路径上最大边权”。

从代码角度来说，倍增表里的mx[j][x]定义要特别小心。我习惯让mx[0][v]在 DFS 时等于“从 v 到它父节点那一条边的权值”，然后递推式写成：

f[i][x] = f[i-1][ f[i-1][x] ]; mx[i][x] = max(mx[i-1][x], mx[i-1][ f[i-1][x] ]);

这个递推的意思是：从 x 向上跳 2^i 步的最大边权，等于先跳 2^(i-1) 步这一段的最大边权、再跳剩下 2^(i-1) 步这一段的最大边权，两者取最大。注意第二项必须先知道f[i-1][x]才能取到，所以我写的时候会把两行顺序固定好，防止自己手滑。

3.3 完整代码与复杂度说明

下面这份代码是我比赛时写出来的完整版本，主流程没有用任何花哨技巧，就围绕“读边建树 + 树上倍增”两个核心。代码已经去掉了无关注释，方便直接对着理解。

#include <bits/stdc++.h> using namespace std; const int N = 200005; const int M = 400005; const int LOG = 20; int n, m, K; int head[N], ver[M], nxt[M], val[M], tot; int fa[N]; int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); } void addEdge(int u, int v, int w) { ver[++tot] = v; val[tot] = w; nxt[tot] = head[u]; head[u] = tot; } int dep[N]; int f[LOG][N]; int mx[LOG][N]; void dfs(int x, int pa) { dep[x] = dep[pa] + 1; f[0][x] = pa; for (int i = 1; i < LOG; ++i) { f[i][x] = f[i - 1][ f[i - 1][x] ]; mx[i][x] = max(mx[i - 1][x], mx[i - 1][ f[i - 1][x] ]); } for (int e = head[x]; e; e = nxt[e]) { int v = ver[e]; if (v == pa) continue; mx[0][v] = val[e]; dfs(v, x); } } int queryMax(int u, int v) { int res = 0; if (dep[u] < dep[v]) swap(u, v); int d = dep[u] - dep[v]; for (int i = 0; i < LOG; ++i) { if (d & (1 << i)) { res = max(res, mx[i][u]); u = f[i][u]; } } if (u == v) return res; for (int i = LOG - 1; i >= 0; --i) { if (f[i][u] != f[i][v]) { res = max(res, mx[i][u]); res = max(res, mx[i][v]); u = f[i][u]; v = f[i][v]; } } res = max(res, mx[0][u]); res = max(res, mx[0][v]); return res; } int main() { scanf("%d%d%d", &n, &m, &K); for (int i = 1; i <= n; ++i) fa[i] = i; for (int i = 1; i <= m; ++i) { int u, v; scanf("%d%d", &u, &v); int fu = find(u), fv = find(v); if (fu != fv) { fa[fu] = fv; addEdge(u, v, i); addEdge(v, u, i); } } // 森林预处理，所有未被访问的连通块都要遍历 for (int i = 1; i <= n; ++i) { if (dep[i] == 0) dfs(i, 0); } while (K--) { int u, v; scanf("%d%d", &u, &v); if (find(u) != find(v)) { puts("-1"); } else { printf("%d\n", queryMax(u, v)); } } return 0; }

建树阶段是 O(M α(N))，DFS 预处理是 O(N log N)，每次查询是 O(log N)。整体上跑 2e5 的数据非常轻松。

4. 写代码和测数据时持续踩坑的四个细节

4.1 森林不要按单棵树来 DFS

这个坑我第一次写时踩了。题目并不保证所有星球最终都连通，所以我建的是一整片森林，不是一棵树。如果我从节点 1 开始 DFS，就只会遍历到节点 1 所在的那个连通块，其他连通块里的点dep全部还是 0，LCA 查询时全部乱套。

解决办法很简单，就是用dep[i] == 0作为“未访问”标记，for 循环把 1 到 n 全部扫一遍，遇到没访问过的点就dfs(i, 0)。孤立点也会被正常处理，它们的dep会被置为 1，f 数组也会被初始化。这一步非常关键，哪怕只有一个点没被初始化，后面查询都可能越界或返回错误答案。

4.2 路径最大值与倍增表更新顺序的坑

mx[i][x]的递推依赖f[i-1][x]，所以必须先把f[i][x]算出来，再算mx[i][x]。我之前有一版代码手滑把两行写反，结果mx[i][x]的第二项恒为 0，测试小数据时因为路径边权小还不容易发现，一上大数据就各种错误答案。

还有一个更隐蔽的细节：查询过程中，无论是跳深度还是跳 LCA，都要先取res的最大值，再更新当前节点。如果先跳节点后取边权，就会漏掉已经跳过的那一段路径上的最大边权。我一般在写queryMax时，会把“统计”和“上跳”两个动作严格按先后顺序固定成：先res = max(res, mx[i][u])，再u = f[i][u]。这样逻辑清晰，也不容易错。

4.3 并查集别顺手路径压缩后丢掉合并信息

建树的代码里，我是边读边建树，同时在并查集里做合并。这个并查集在完成建树之后，它的最终状态就是整张图的最终连通块划分。回答每个询问时，第一步就find(u) != find(v)判断是否连通。

有些同学会在这个地方犯糊涂：他们在建树完成之后，又想着“要不要再把那些丢失的边加进并查集重新连一遍”。完全没必要。因为并查集经过前面的建树过程，已经忠实地记录了所有合并边的合并结果。丢失的边不会改变连通性，所以最终状态就是对的。这时候再动并查集，纯属画蛇添足。

4.4 数组大小与读入优化的选择

树边最多只有 N-1 条，因为我只在“合并边”的时候加树边，所以邻接表开两倍 N 就足够，也就是 2*(N-1) 条边。原始输入里的 M 条边大部分可能被丢弃，不用为它们保留邻接表空间。我第一次用 N 作为邻接表大小，直接在 N=2e5 时越界，查了十分钟才定位到。

至于读入，题目标注Standard IO，意思是标准输入输出，不需要freopen。2e5 这个规模其实scanf也能过，但如果你的代码里还用了递归 DFS 和 STL，那么快读会给你更多余量。我平时会把一个简单的快读函数直接放在代码头部，也不费事，算是个人习惯。

inline int readInt() { int x = 0; char c = getchar(); while (c < '0' || c > '9') c = getchar(); while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = getchar(); } return x; }

5. 一次引申：同一个模型还能换着法再考

5.1 这题和“最小瓶颈路”其实是同一张脸

做完这道题之后我回头翻笔记，发现“求两点间路径上最大边权最小”的最小瓶颈路问题，解法也是在最小生成树上求路径最大值。本道题只是把最小生成树里的“按边权排序”换成了“按输入时间顺序出现”，其余步骤一模一样。如果你已经会最小瓶颈路，那么这题对你来说就是在 LCA 模板上改两行的功夫。

这也在提醒我，刷题不能只背题型，要把题目抽象成模型。今天考的“时间生成森林”，明天换一身衣服，可能就是“最小瓶颈路”、“最小生成树上的虚树”，甚至“Kruskal 重构树”。核心永远是那句：树边压缩了连通性，边权记录了关键时刻。

5.2 如果询问改成“在 t 时刻是否连通”，做法会完全不同

假设题目不是问“最早第几条边连通”，而是问“在第 t 轮时 u、v 是否已经属于同一个联盟”，那解法反而更简单：把所有边按时间顺序排好，所有询问按 t 排序，一遍扫描加边、并用并查集回答当前时刻的询问即可，连 LCA 都不需要。时间复杂度是 O((M + K) α(N))，更低。

之所以这题要用生成森林 + LCA，关键就在“首次连通”这个时间点。要想回答“首次”，最核心的障碍是：不能只维护当前连通性，还要知道“哪条边打破了两个连通块之间的壁垒”。而生成森林恰好把每一次“破壁”都保存成了带时间戳的树边，所以能回答任意两点之间的最早连通时间。

5.3 可持久化并查集和整体二分什么时候才更优

我也见过有人拿可持久化并查集来做这题，思路是：把每次合并的版本存下来，查询时在某个版本的并查集里判断连通性，再二分答案。理论上可行，但可持久化并查集实现复杂，空间开销还要多一个 log，代码长度几乎是生成树解法的三倍，调试难度更是直线上升。整体二分也能处理“第几次连通”类问题，但在这题里属于杀鸡用牛刀。

我的体会是，比赛里选择解法不能只追求绝对正确，还要考虑代码稳健性和调试成本。如果一个方法能通过所有数据但代码复杂到可能写挂，另一个方法思路清晰、代码量少，我会坚定选后者。这道题的生成森林 + LCA 就是那种“短、稳、快”的解法。

后来我额外用可持久化并查集把整道题完整敲过一遍，算是为了复习数据结构。两版代码放一起对比，差距不是在运行时间，而是在“人脑负担”上。生成树版本我基本一次写对，而可持久化可并查集版本调了将近两个小时，最后也只换来不到一个数量级的复杂度优势，得不偿失。如果你手头刚刷完并查集和 LCA，这道题真的是很好的练习素材：每一步推导都顺理成章，代码也不长，却把两个经典知识点的组合拳打得明明白白。