企业官网建设流程全解析

边权转点权、边的染色，这两个词放在一起，乍看像两个名词生硬地缝合成了一道题。我第一次碰到它时，盯着题面看了半天，以为要写复杂的边染色算法。后来在某届互联网公司算法竞赛复赛里被一道叫《边的染色》的题教育了，才反应过来：这题真正考的是把一个图上每条边的约束，搬到顶点上去。

具体说，就是给定一张无向图，每条边有一个 0/1 颜色。要求给每个顶点也标上 0/1，使得对任意边 (u,v)，都有val[u] xor val[v]等于这条边的颜色。如果两种颜色分别看成 0 和 1，红色表示端点颜色不同，蓝色表示端点颜色相同，那题目就变成了一组异或方程组。这个技巧对刷图论、并查集、DFS 的竞赛选手特别有用，对想打通树上差分、路径异或查询的人同样值得一看。

1. 先拆题：为什么边的染色能变成点权约束

1.1 边的颜色只是两端点状态的“差异”

很多人一听“边染色”就默认是要给边分配颜色，但这题恰好反着来：边上的颜色是已知条件，我们要求的是顶点颜色。

设点权取 0 或 1，边权 w 也取 0 或 1。约束为：

val[u] xor val[v] = w

如果 w=1，说明 u 和 v 的颜色必须相反；如果 w=0，说明 u 和 v 的颜色必须相同。换句话说，边权记录的是两个端点之间的差异，而不是边本身独立的一个值。

这就带来一个关键视角：只要把每个顶点的状态确定下来，所有边的颜色都会自动确定。反过来，如果每条边的颜色都已知，我们要找的其实是一组满足差异关系的顶点状态。这种把边上信息搬到点上的动作，就是边权转点权。

1.2 点权本质是异或方程组的势能表示

把每条边看成一个方程，整张图其实就是一组异或方程组：

x_u xor x_v = w_e

未知数是 n 个顶点的颜色，方程数是 m 条边的约束。固定一个根，令它的点权为 r，然后沿任意一条路径往外推，每个点的值都可以写成：

val[v] = r xor (根到 v 的路径边权异或和)

所以点权并不是“凭空多出来”的东西，它本质上是异或方程组的一组解。边权则是相邻两个点权之间的差分。

可以把它类比成海拔和高差：每条边的权值是两地点之间的高差，点权是每个地点的海拔。只要任意一条闭合路线的高差加起来等于 0，整张图就可以由某个根的海拔推出所有海拔。这样思考之后，DFS 染色和带权并查集就都顺理成章了。

2. 解法一：DFS一遍染色，从根一路推出所有点权

2.1 DFS 怎么把整张图的值推出来

最朴素的解法是直接建图，然后对每个连通块跑 DFS。

算法的核心很直接：

1. 任选一个未访问点作为根，假设它的点权为 0，标记为已访问。
2. 枚举根的所有邻接边 (u,v,w)。
3. 如果 v 还没访问，就令val[v] = val[u] xor w，然后递归处理 v。
4. 如果 v 已经访问过，就检查当前推导结果是否和已有值一致：val[v] == val[u] xor w必须成立。
5. 每个连通块都处理完后，如果所有检查都通过，则有解。

这里的“检查已访问点”非常关键。DFS 过程中经过的边会形成一棵生成树，生成树上的边用来给点赋值；非树边则全部用来做冲突检测。只要有一条非树边不满足约束，整张图就无解。

C++ 代码大概长这样：

vector<int> val(n, 0); vector<int> vis(n, 0); bool ok = true; function<void(int, int)> dfs = [&](int u, int cur) { val[u] = cur; vis[u] = 1; for (auto [v, w] : g[u]) { int expect = cur ^ w; if (!vis[v]) { dfs(v, expect); } else if (val[v] != expect) { ok = false; } } }; int comp = 0; for (int i = 0; i < n; i++) { if (!vis[i]) { comp++; dfs(i, 0); if (!ok) break; } }

注意一个细节：每个连通块的根都可以选 0 或 1。DFS 时统一从 0 开始，只是因为我们只输出其中一套解。如果要统计方案数，必须把根颜色任取带来的倍数算进去。

2.2 非树边、自环、重边三个容易漏的检查点

我第一次写这套 DFS 时，样例过了，提交却 WA。调了半天才发现，问题全出在非树边检查上。

自环也要单独看。自环是 (u,u,w)，约束变成：

val[u] xor val[u] = w

左边恒等于 0，所以只有 w=0 时自环才不产生矛盾。如果题目数据里出现 w=1 的自环，直接无解。

重边同理，每条重边都是一条独立的约束，必须逐条检查。哪怕有一条重边不满足当前点权，都不能算有解。DFS 里循环邻接边时天然会处理重边，但如果你为了省内存去重，反而可能丢掉冲突信息。

还有一类问题来自vis数组的误用。有人喜欢直接用val初始化为 -1 表示未访问，然后判断val[v] == -1。这种做法本身没问题，但千万别默认未访问点的点权是 0。点的真实颜色可以是 0，也可以是 1，只有“是否访问过”这个状态才能决定要不要给它赋值。

2.3 统计连通块数量得到方案数

如果没有冲突，答案也很好算。

每个连通块中，只要根的点权取 0 或 1 任意一个，其他所有点的值都会被唯一确定。根选 0 得到的方案和根选 1 得到的方案，恰好是整块全部翻转，两者完全不同。

所以有解时，方案数是：

2^{连通块数量}

孤立点也算一个连通块。它的点权可以任意取 0 或 1，不会影响任何边约束，因此每个孤立点都给方案数贡献一个 2 倍因子。

如果题目要求对结果取模，直接用快速幂计算2^comp mod M。如果题目只要求输出任意一组方案，DFS 求出的val数组就是一组合法解，不需要再额外翻转。

3. 解法二：带权并查集，把异或约束当关系合并

3.1 为什么并查集也能解异或方程组

DFS 适合静态建图，但如果题目要求在线加边，或者你不想建邻接表，带权并查集是另一个非常顺手的工具。

并查集维护的是“集合”，而带权并查集在集合关系之外，额外维护每个点到集合根的异或值。对一条边 (u,v,w)，它其实描述了 u 和 v 之间的相对关系：

val[u] xor val[v] = w

如果 u 和 v 还不属于同一集合，就把两个集合合并，同时记录新根之间的相对异或值；如果已经属于同一集合，就检查已有关系是否和新边矛盾。

这个思路把每条边当成一条“在线约束”，而不是显式地把图存下来，非常适合边数很多、点数很多的场景。

3.2 两个关键数组和一条合并公式

带权并查集通常维护两个数组：

• fa[x]：x 的父节点。
• xr[x]：val[x] xor val[fa[x]]。

在find做路径压缩时，需要同步更新xr。压缩之后，xr[x]的含义变成val[x] xor val[根节点]。

合并时，假设 x 所在集合根是 rx，y 所在集合根是 ry。约束为：

val[x] xor val[y] = w

把val[x] = xr[x] xor val[rx]、val[y] = xr[y] xor val[ry]代进去，可以得到：

val[rx] xor val[ry] = w xor xr[x] xor xr[y]

因此，如果把 rx 合并到 ry 下面，令fa[rx] = ry，那么应该设置：

xr[rx] = w xor xr[x] xor xr[y]

完整的 C++ 模板：

struct DSU { vector<int> fa, xr; DSU(int n) { fa.resize(n); xr.assign(n, 0); iota(fa.begin(), fa.end(), 0); } int find(int x) { if (fa[x] == x) return x; int p = fa[x]; int r = find(p); xr[x] ^= xr[p]; fa[x] = r; return r; } bool unite(int x, int y, int w) { int rx = find(x); int ry = find(y); if (rx == ry) { return (xr[x] ^ xr[y]) == w; } fa[rx] = ry; xr[rx] = w ^ xr[x] ^ xr[y]; return true; } };

需要特别提醒：find里必须先记录原来的父节点，再递归找根，然后用原父节点的xr去更新当前节点的xr。顺序写错，路径压缩后的异或值就全错了。

处理完全部边后，统计剩下多少个根节点，也就是fa[i] == i的节点数量。每个根可以任选 0/1，所以方案数同样是2^{根的数量}。

3.3 DFS 与并查集怎么选：一张表对照

如果是竞赛现场，我的习惯是：题目已经给出完整边集，优先 DFS，实现简单不容易错；如果题目边是一个一个动态给的，或者图特别大怕爆栈，就用带权并查集。

4. 扩展思路：树路径异或与多位边权的处理

4.1 树上的边权转点权是路径异或查询的基石

边权转点权不只在“边的染色”这类题目里出现。树上路径异或查询，本质上也是同一个技巧。

给定一棵树，每条边有权值 w。选一个根，预处理每个点到根路径上的边权异或和dis[u]。于是任意两点 u,v 之间路径的边权异或就是：

dis[u] xor dis[v]

不需要再单独处理 LCA 对应的那一段边权。原因很简单：u 到根和 v 到根的重叠部分，在异或运算中被抵消了。

这个结论在树链剖分、树上差分、最近公共祖先相关问题里到处可见。做完这道边的染色，再去看这类题，会有一种“原来都长一样”的感觉。

4.2 无解的本质：每个环的边权异或必须为 0

为什么 DFS 要到非树边做检查，为什么要用带权并查集判断矛盾？因为无解的本质是：图上任何一个环，环上所有边权异或起来必须等于 0。

如果存在一个环，环上权值异或不为 0，就找不到一组点权能同时满足所有边。反过来，只要所有环都满足这个条件，就一定有解。

用生成树视角看：选一棵生成树，树边确定了所有点的相对值。每条非树边会产生一个基本环。DFS 检查非树边时，就是在动态验证这个基本环异或是否为 0。带权并查集也是在边加入的过程中维护这种闭环约束。

如果你想加深理解，可以自己画一个三角形：三条边权分别是 1、1、1。无论根取 0 还是 1，都会出现矛盾，因为 1 xor 1 xor 1 = 1，不是 0。这个例子能很直观地解释什么叫“环的异或和必须为 0”。

4.3 当边权变成多位整数时怎么办

如果题目里的颜色不是两种，而是 K 位二进制整数，边权约束变成：

val[u] xor val[v] = w

w 是一个整数，公式依然成立。因为异或运算是按位独立的，每一位可以单独看成 0/1 染色问题。两种处理方式：

第一种，拆位。把每条边的权值拆成 K 位，对每一位分别做一次 DFS 或并查集，全部通过则有解。

第二种，直接用带权并查集维护整数的异或值。上面的模板不需要改，xr数组从 bool 改成 int 就行。合并公式里的w xor xr[x] xor xr[y]对整数同样有效。

如果点权的范围被限定在[0, 2^K-1]，每个连通块根的选择就有2^K种，方案数是(2^K)^{连通块数}。只做 0/1 染色时，K=1，正好回到前面的结论。

4.4 输出点权方案时的注意点

如果题目要求输出一组方案，而不是方案数，也有两个细节。

DFS 已经算出来的val就是一组合法方案，直接输出即可。带权并查集则需要先把每个根的点权定为 0，再通过val[x] = xr[x] xor val[root]还原每个点的值。这里必须先把所有根的值确定好，再统一还原，否则边查询边还原容易引用到还没定值的根。

另外，新增边的顺序不会影响最终正确性，但会影响并查集合并的形态，从而影响输出的点权具体长什么样。题目一般只要求任意方案，所以不需要关心这种差异。

5. 踩坑记录：边权转点权最容易错的地方

5.1 四个让我 WA 到崩溃的细节

第一，vis和val要分清。很多人一开始把val初始化为 0，然后用if (val[v] == 0)判断有没有访问过。但根节点取值恰好可能为 0，导致二次访问被当成未访问，图中出现环时直接死循环或漏判。正确做法是用独立的vis数组，或者把val初始化为 -1。

第二，非树边检查不能省。DFS 给点赋值时，生成树内部的边是用来推值的；那些已经访问过的邻居，必须核对一次期望值。我见过很多模板只递归未访问点，完全不管已访问点，样例能过，数据一大就 WA。

第三，自环和重边经常被忽略。自环要求边权为 0，不为 0 直接无解。重边必须逐条参与检查，不能偷懒只保留一条。

第四，带权并查集的路径压缩顺序。find里如果先改fa[x]再取xr[p]，拿到的就不是原来父节点到根的异或值了。正确写法是先保存原父节点，完成递归后，用原来的xr[p]更新xr[x]，最后再改fa[x]。

5.2 一个可复现的反例 debug

我调试这种题时会固定用一个反例：三个点，三条边构成三元环。

0-1 边权 1 1-2 边权 1 0-2 边权 1

从根 0 出发，令val[0]=0。通过 0-1 得到val[1]=1，通过 1-2 得到val[2]=0。此时检查边 0-2，期望val[0] xor val[2] = 0 xor 0 = 0，但实际边权是 1，于是冲突，无解。

如果把第三条边改成边权 0：

0-1 边权 1 1-2 边权 1 0-2 边权 0

同样的推导，val[2]=0，边 0-2 的期望值0 xor 0 = 0，与实际一致，有解。这个三元环样例虽然简单，却能同时验证 DFS 的非树边检查和并查集冲突合并逻辑。

5.3 调试与对拍建议

最后分享一个我自己的对拍思路。

先写一个暴力程序，枚举所有2^n种点权，然后逐条边验证。数据规模小的时候，这个暴力程序是最可靠的判题器。再写一个基于 DFS 或并查集的解法，随机生成小图，让两个程序跑同样的数据，结果不一致就说明解法有 bug。

对拍时随机生成器要注意生成自环、重边和非连通图，因为这些边界数据最容易暴露问题。生成 1000 组数据，比对通过，基本可以放心提交。

我个人在实际调试中的体会是：这类题的难点不在算法本身，而在“信不信这个转化一定正确”。一旦你足够熟练，看到边上的颜色和异或约束，第一反应就应该是给每个点选一个势能值，让边权变成势能的差。这个思路在后续遇到树上路径异或、带权并查集、差分约束的时候，还会反复出现。