企业官网建设流程全解析

最近群里有人甩过来一道题，标题就叫“白魔法师”。点进去一看，树结构、黑白点，还贴着 DFS 和并查集两个标签。乍一看像是图论遍历题，仔细做下来发现，核心其实是并查集维护连通块 + 一次全树扫描。这种“预处理白块、枚举黑点”的套路，在很多题里都能复用，值得拆开讲透。

如果你正在准备算法竞赛，或者刷题遇到“改变一个点，合并周围同色连通块求最大”这种描述，这篇可以帮你把思路顺下来。我不只讲答案，还会把并查集为什么能这么用、边界情况怎么处理、实际写代码时哪些坑必须避开，全部过一遍。

1. 题目到底在问什么：最大白色连通块

1.1 一句话还原题意

有 n 个节点的一棵树，每个节点初始要么白、要么黑。规则很简单：你可以施展一次魔法，把任意一个黑色节点变成白色，注意最多只能变一次，也可以选择不变。目标是在这次变白之后，让整棵树里某个白色连通块尽可能大，问这个最大节点数是多少。

这个描述我最初读的时候，差点被“魔法”带偏，以为要做什么复杂的染色模拟。其实把魔法翻译成算法语言，就一句话：枚举一个黑点，把它改成白色后，和它相邻的所有白色连通块会“缝合”成一个更大的白色区域。我们要找这个缝合后面积最大的情况。

1.2 为什么不直接暴力

拿到题先别急着写。最容易想到的方案是：枚举每一个黑色节点，把它临时涂白，再从它出发做一次 DFS/BFS 统计白色连通块大小，统计完再改回来。这个思路完全正确，但代价是 O(n²)。如果 n 只有 1000，那随便写；但这类题 n 通常给到 10⁵ 甚至 2×10⁵，O(n²) 必挂。

为什么暴力会浪费？关键在于，树里绝大多数白色连通块是固定不变的，重复扫描会把同一批白点反复统计很多次。我们真正要算的，其实是每个黑点能“拉拢”过来的那些白色邻居分别有多大。这就给出了一个优化方向：先把所有白色连通块的大小一次性算好，再枚举黑点只看它的邻居，把相邻白色块的大小加起来。

这也是标题里“并查集”出现的原因。白色连通块可以用并查集维护，每个白点所在的“块”是谁、块里有多少点，预处理完都是 O(1) 查询。

1.3 这个模型的直觉

你可以把白色连通块想象成一个一个“白色社团”，每个社团都有一个群主，群主用根节点代表，群成员数量就是 sz。初始时，所有相邻的白点已经互相拉入同一个群。现在有一个黑色节点，它想变白，那就看它周围有哪些白色社团，一旦它变白，这些社团和它自己会合并成一个更大的社团。

所以答案的计算公式特别干净：

对任意黑点 u，假设它周围不同白色连通块的大小分别是 s₁, s₂, ..., sᵏ，那么施法后得到的白色连通块大小就是 1 + s₁ + s₂ + ... + sᵏ。对所有黑点取最大值，再和“一次魔法都不用”的原始最大白色块大小做比较，就是最终答案。

2. 核心算法拆解：并查集管“块”，遍历管“邻居”

2.1 并查集在这里承担什么角色

很多同学一看到树，第一反应是用树形 DP 或者 DFS 序。这题确实不能完全抛开 DFS，但核心的连通块归属问题用并查集解决最舒服。并查集要做的只有一件事：把整棵树中所有相邻的白色节点两两合并。

操作方式有两种。一种是把边全部存下来，读完后再遍历边，如果一条边的两个端点都是白色，就执行 union 操作。另一种更省事，读边的过程中直接判断端点颜色，都是白就合并。我推荐后一种，因为颜色数组在边之前输入，信息已经齐了，边读边合并不需要额外存边表。

并查集的每个集合，对应一个白色连通块，size 数组记录这个块的大小。这里有个细节：size 只对根节点有意义，用的时候应该是 size[find(x)]，而不是 size[x]。x 经过路径压缩后，它的父节点直接指向根，但 size[x] 可能早在合并过程中就失效了，千万不要在统计的时候用错。

2.2 枚举黑色节点时怎么计算贡献

白色块准备好之后，第二次遍历才是真正的“魔法操作”。这次要遍历所有黑色节点 u，逐一检查它的邻居 v。如果 v 是白色，就找到 v 所在白色块的根 root = find(v)，然后把 root 加入一个集合；最终把所有不重复的 root 对应的 size 累加起来。

这里有个很容易踩的坑：一个黑色节点可能连着同一个白色连通块的多条边。虽然在一棵树里，这个情况其实不会发生，因为如果两个白点通过同一个黑点相连，它们又通过白色路径连通，就会形成环；但如果你把这个套路迁移到一般图，或者你写的时候手一抖没有判重，就可能把一个白色块的大小重复加上去。所以稳妥做法是，每个黑点用一个 set 收集不同的根，或者用一个时间戳数组做去重。

去重之后，cur = 1 + sum(sz[root])，这个 1 是当前黑点本身变白的贡献。然后用 cur 更新全局答案。因为不同黑点枚举时是独立计算的，不需要真的把某个点永久改白，所以不需要回滚操作。

2.3 为什么不需要重复 DFS

这题标题挂着 DFS，但如果你按经典 DFS 去遍历每个黑点再统计，还是逃不掉 O(n²)。真正合理的做法是：全树只做两遍扫描。第一遍负责建立并查集关系，第二遍枚举黑点收集相邻白色块。树是稀疏图，遍历一遍所有节点和边，总复杂度就是 O(n α(n))。

如果不用并查集，你也可以先用 DFS 给每个白色连通块编号，记录每个编号的大小，再枚举黑点。本质上和并查集是一样的：DFS 是显式地给连通块打标签，并查集是动态地合并标签。区别在于，并查集实现更短，而且不需要担心递归深度过大导致爆栈。实际比赛中，我更喜欢并查集，因为只要处理好 find 和 union 两个函数，剩下的逻辑非常线性。

3. 从零实现：C++ 代码与每一步解读

3.1 数据结构准备

C++ 代码如下，用的是最常见的 vector 邻接表 + 并查集数组。为了省空间，颜色数组直接用 char，读入时用 'W' 表示白色，'B' 或 '0' 表示黑色，具体看题目输入格式。

#include <bits/stdc++.h> using namespace std; const int MAXN = 200005; vector<int> g[MAXN]; char color[MAXN]; int fa[MAXN], sz[MAXN]; int n; int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); } void unite(int a, int b) { int ra = find(a), rb = find(b); if (ra == rb) return; if (sz[ra] < sz[rb]) swap(ra, rb); fa[rb] = ra; sz[ra] += sz[rb]; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) { cin >> color[i]; fa[i] = i; sz[i] = 1; } for (int i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); if (color[u] == 'W' && color[v] == 'W') { unite(u, v); } } int max_white = 0; for (int i = 1; i <= n; i++) { if (color[i] == 'W') { max_white = max(max_white, sz[find(i)]); } } int ans = max_white; for (int u = 1; u <= n; u++) { if (color[u] == 'W') continue; set<int> roots; for (int v : g[u]) { if (color[v] == 'W') { roots.insert(find(v)); } } int cur = 1; for (int r : roots) { cur += sz[r]; } ans = max(ans, cur); } cout << ans << '\n'; return 0; }

3.2 第一步：合并白色连通块

读入阶段，我一边输入边，一边判断端点颜色。如果两个端点都是白色，说明它们在同一个白色连通块里，直接 unite。这里有一个前提：颜色数组必须先于所有边读入，否则读边时你不知道 endpoint 颜色。题目如果反过来先给边再给颜色，那就得先把边存到临时数组里，读完颜色后再统一合并。

初始化 fa[i] = i、sz[i] = 1 这一步不能省。并查集最忌讳的就是没有初始化就直接 find，那会访问野指针，调试起来非常痛苦。如果你在本地没跑起来，先检查是不是哪个数组没初始化。

3.3 第二步：计算初始最大白色块

在一开始，我们要先算出“一次魔法都不用”时候的答案，也就是整棵树里最大的白色连通块。遍历所有节点，如果节点是白色，就取 sz[find(i)] 的最大值。

这个步骤很多人会漏。因为题目说“最多一次”，所以可以选择不用。如果整棵树已经有一个很大的白色区域，而所有黑色节点周围的白色块加起来都不如它，那答案就是原始值。特别地，如果所有节点本来就是白色，ans 会等于 n，程序输出 n，正确。

3.4 第三步：枚举黑点更新答案

新建一个空的集合 roots，遍历黑点 u 的所有邻居。每遇到一个白色邻居 v，就把 find(v) 这个根插进集合。注意 set 里存的是根节点编号，不是节点本身。这样可以在多个邻居来自同一块时自动去重。

然后 cur = 1，再遍历集合，把每个根的 sz 累加进去。这里 cur 初始为 1，代表当前黑色节点 u 自己变白。如果 u 周围没有任何白色邻居，cur 就是 1，对应的含义就是：把一个孤立黑点变白后，只形成大小为 1 的白色块。这种情况在“整棵树全黑”的测试点里会出现。

最后 ans = max(ans, cur)。由于我们遍历了所有黑点，所以最终 ans 就是“使用至多一次魔法”后的最大白色连通块大小。

4. 实战中的坑与问题排查

4.1 重复合并、重复统计怎么避免

并查集本身的 unite 函数里，第一步就是先 find 两个端点，如果根相同直接返回。这保证了相邻白点不会因为重复输入边而重复合并。但还有一种重复统计是出现在枚举黑点时，理论上树不会出现，但加 set 最安全。

我在第一次写这个题的时候就吃过亏：某个黑点连着两个白色邻居，这两个邻居其实属于同一个白色连通块，我直接用累加没判重，结果把同一个块算了两次，样例一过，提交就错。后来查出来是因为我用错了数据结构——原题树结构其实不会出现这种情况，但我当时造了一个非树的自测数据，把自己的代码暴露了。所以规则很简单：凡是“同一个元素不能重复贡献”的场景，一律去重，宁可多写一个 set，也不赌数据。

4.2 并查集的路径压缩与按秩合并

并查集如果不做路径压缩，最坏情况下 find 会退化成 O(n)，整个程序变成 O(n²)，和暴力没区别。标准写法是 find 里顺手 fa[x] = find(fa[x])。按秩合并我用的是 sz 启发式合并，也就是把较小集合合并到较大集合里，这样树的高度可控。

有一个经验性的检查点：如果你发现程序在大数据点超时，先看 find 是不是没有路径压缩。还有，如果并查集合并时把 sz 加错了方向，比如总是 sz[ra] += sz[rb]，但没有考虑 ra 和 rb 可能顺序反了，也会导致根节点 size 维护出错。建议在合并前先交换，让 sz 大的做根，再更新。

4.3 递归爆栈与遍历方式的选择

题目叫“DFS&并查集”，很多初学者会尝试用递归 DFS 去处理树，但 n 到 10⁵ 的中等规模，C++ 默认递归栈很容易爆。这个题其实根本不需要递归，因为并查集的建立靠的是边表遍历，黑点的枚举也靠的是邻接表遍历，两者都是循环，不是 DFS 递归。

如果你实在想用 DFS 给白色块编号，那就必须考虑栈空间问题。现实中我一般两个选择：一是把递归改成手写栈的迭代 DFS，二是直接换并查集方案。像“白魔法师”这类题，并查集方案更短，而且不需要担心爆栈，所以我在实战里通常直接选它。

4.4 常见问题速查表

5. 把过程走一遍：几个关键例子

5.1 黑点连接两个白色块

假设有 5 个节点，颜色是 W B W B W，边是 1-2、2-3、3-4、4-5。初始白色连通块有两个：节点 1 单独一块，节点 3 和节点 5 被黑色节点 4 隔开，所以节点 3、5 不是同一个块。块大小分别是 1 和 1（3 和 5 独立），最大白色块是 1。

枚举黑点 2：邻居是 1 和 3，分别属于两个白块，cur = 1 + 1 + 1 = 3。枚举黑点 4：邻居是 3 和 5，两个白块，cur = 1 + 1 + 1 = 3。最终 ans = 3。这个例子的语义是：把中间某个黑点变白后，它左右两个白点连同自己焊成一个长度为 3 的白色段。

5.2 全黑、全白与只有一个白点

全黑时，每个黑点变白后周围没有白点，cur = 1，所以输出 1。这里要注意 ans 的初始值。如果你把 ans 初始化为 0，遍历黑点后 cur 至少是 1，最终也能得到 1，所以没问题。但如果你在统计时不枚举黑点而直接输出 max_white，就会输出 0，逻辑错误。全白时，没有黑点可枚举，ans 就是初始 max_white = n，输出 n，符合“不用魔法就是全体白点连通”。

只有一个白点、其余全是黑点时，初始 max_white = 1。如果某个黑点恰好连着这个唯一白点，cur = 1 + 1 = 2，也就是变黑为白后，白点串成一个长度为 2 的块；如果黑点连不到白点，cur = 1。最终 ans 是多少取决于拓扑结构。这提醒我们：答案不一定总是“白点总数”，有时增加一个白点反而不能扩大连通块。

5.3 这套思路能迁移到哪些题

“白魔法师”本质上属于一类问题：给定若干同色连通块，允许一次操作把一个点“变色”，求操作后同色连通块最大值。这类题的通用解法就是先预处理所有连通块，再枚举可操作的点，统计它周围的块贡献。

如果题目改成“可以把 k 个黑点变白”，那就不只是简单求和了，因为多个黑点之间还可能隔着白块相互连通，需要更复杂的背包或动态规划。但只要你理解了“变一个点=合并周围同色块”这个核心，后面扩展时思路不会乱。

6. 赛前小技巧与个人习惯

6.1 先画图，再写代码

我每次做这种图论题，都会在草稿纸上画一棵 5 到 7 个节点的树，把白点圈出来，然后手动算一遍标准答案。画图能直观看到哪些信息需要预处理，哪些信息是遍历时现算的。白魔法师这个题，如果不动笔直接写，很容易在“要不要用 set 去重”“ans 要不要初始化为 max_white”这些细节上犯迷糊。

6.2 打印并查集根和大小

调试阶段，我会在预处理后把每个白点的根节点和块大小打印出来看一眼。比如输出“节点 3 的根是 2，块大小是 5”，这样能快速确认合并是否正确。很多时候答案不对，不是枚举逻辑的问题，而是并查集 size 维护错了。打印这一步能节约大量时间。

6.3 关于 DFS 的一个提醒

标题里的 DFS 并不是一定要写一个递归函数。树的遍历方式很多，本题真正需要的是“对每个节点访问其所有邻居”，这本身就是一次深度优先遍历的过程。如果你习惯递归，可以写 DFS；如果担心性能，就直接 for 循环扫邻接表。重点是维护好连通块信息，而不是纠结遍历形式。

我自己在实际比赛中更倾向于把并查集作为主武器，把遍历当作副武器。一次建块，一次枚举，复杂度低，代码稳定。这个套路练熟之后，像“最多改变一个点求连通块最大”的变种题，基本都能在几分钟内写出来。