某次联考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 (NM)) 左右仍然是上亿次并查集操作而且每轮二分都要重新初始化并查集数组常数非常大。更关键的是这种做法还没触及题目的核心——题目要的是“首次连通的时间”不是“在某个给定时刻是否连通”所以就算你把所有询问按时间排序、把边一条条加进去也没法直接回答“首次”。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全部还是 0LCA 查询时全部乱套。解决办法很简单就是用dep[i] 0作为“未访问”标记for 循环把 1 到 n 全部扫一遍遇到没访问过的点就dfs(i, 0)。孤立点也会被正常处理它们的dep会被置为 1f 数组也会被初始化。这一步非常关键哪怕只有一个点没被初始化后面查询都可能越界或返回错误答案。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 作为邻接表大小直接在 N2e5 时越界查了十分钟才定位到。至于读入题目标注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这道题真的是很好的练习素材每一步推导都顺理成章代码也不长却把两个经典知识点的组合拳打得明明白白。 
长河君 · 2026/10/13 1:55:26 · 阅读 1.2k 星球联盟题解：时间生成森林与倍增路径最大值
某次联考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 (NM)) 左右仍然是上亿次并查集操作而且每轮二分都要重新初始化并查集数组常数非常大。更关键的是这种做法还没触及题目的核心——题目要的是“首次连通的时间”不是“在某个给定时刻是否连通”所以就算你把所有询问按时间排序、把边一条条加进去也没法直接回答“首次”。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全部还是 0LCA 查询时全部乱套。解决办法很简单就是用dep[i] 0作为“未访问”标记for 循环把 1 到 n 全部扫一遍遇到没访问过的点就dfs(i, 0)。孤立点也会被正常处理它们的dep会被置为 1f 数组也会被初始化。这一步非常关键哪怕只有一个点没被初始化后面查询都可能越界或返回错误答案。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 作为邻接表大小直接在 N2e5 时越界查了十分钟才定位到。至于读入题目标注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这道题真的是很好的练习素材每一步推导都顺理成章代码也不长却把两个经典知识点的组合拳打得明明白白。