企业官网建设流程全解析

聊一个我认为非常有代表性的树形DP题：边的染色。我第一次在2018年某算法竞赛的复赛里看到它时，第一反应是对边做状态压缩，试了十几分钟就发现不对劲——一条边同时连着两个端点，子树的边界一旦切在这条边上，父节点和子节点都要对同一条边负责，状态怎么都不干净。后来看到正解用到边权转点权这个技巧，整个DP从二维缩到一维，代码三十行不到。如果你也曾经在树上DP里被“边”这种单位折磨过，这篇文章应该能给你一个很通用的破题思路。

注意，我这里讲的“边权转点权”不是一种玄学，而是把树上边权问题的决策单位从“边”换成“点”，让每条边都有一个唯一的主人。配合树形DP的状态设计，很多看似绕圈的题都会变得极其直白。下面我按自己当时的思考链路，完整复盘一遍。

1. 这道题到底在问什么：先建立最小红边权值和模型

1.1 模型描述

题面通常可以抽象成这样一个模型：给定一棵n个点的树，每条边有一个权值。现在要把每条边染成红色或蓝色，红色边需要付出这条边的权值作为代价，蓝色边代价为 0。同时要求每个点的邻边集合中，至少存在一条红边。

换句话说：每个点都不能被“蓝环”包围，至少要有一条红色的边从它身上伸出去。目标是最小化所有红边的权值总和。

有的版本可能问方案数，有的版本可能把红蓝边分别给两个权值，但最经典的版本还是最小化红边权值和。我先按这个模型讲，后面再说怎么变形。

1.2 为什么不能直接对边做树形DP

先看暴力：n-1条边，每条边有红/蓝两种选择，枚举所有染色方案的复杂度是O(2^(n-1))，n稍微上到 100 就完全跑不动。树形 DP 自然是首选。

但真正动手设计状态时，问题就来了：树形 DP 要求每个子树的信息能够独立“闭合”，向上传递时只需要一个明确接口。可是边的决策天然有两个端口——一条边(u, v)既是u的邻边，也是v的邻边。如果你把这条边的状态放在子树内处理，子树的边界就会被这条边从中间劈开，父节点的需求、子节点的需求全部纠缠在同一份状态里。

举个具体例子。假设u和它的孩子v之间有一条边e，你在处理v的子树时，为了判断v是否满足“邻边至少一条红”，你必须知道e的颜色。可e同时也是u的邻边，将来合并到u时还要再被看一次。一条边被两个节点共同管辖，这就导致信息无法对称。

1.3 核心矛盾：一条边有两个“主人”

我最初尝试设计dp[u][state]，其中state表示“u与父节点之间的边是红还是蓝”，然后枚举子树内其他边的染色。结果发现子树内那些边的状态虽然可以内部处理，但只要涉及边界边，就一定要把父节点那一侧的需求强行塞进来。状态设计不是说做不出来，而是非常别扭，容易漏。

直到我想明白一件事：想要让边上的决策变得好做，就要给每条边找一个“唯一的主人”。树是无向的，但如果我们任选一个根把树“提”起来，每条边就能按照父子关系降级到子节点身上，边的问题就变成了点的问题。这便是边权转点权的起点。

2. 边权转点权：给每条边找一个唯一的主人

2.1 转化规则：边权下沉到子端点

任选一个节点作为根，比如节点1。把树变成一棵有根树后，每条边(parent[x], x)都可以唯一地挂到深度更大的那个端点x上。也就是说，每个非根节点恰好对应一条从它指向父节点的边。

于是我们建立一个“点权”数组：对于非根节点x，w[x]就是边(parent[x], x)的权值；根节点没有父边，可以认为w[root] = 0。

这样做的好处是：原来一条边同时被两个端点惦记，现在每条边都只属于它的子端点。边的颜色选择，就等价于每个非根节点选择自己是“红点”还是“蓝点”。

2.2 边染色 ↔ 点染色的一一对应

如果非根节点x被标成红点，意味着它对应的父边是红色；如果标成蓝点，意味着父边是蓝色。根没有父边，所以根不参与这个标记。

举个例子，一棵 4 个点的树，根为 1，边为(1,2), (2,3), (2,4)。约定边权分别挂到 2、3、4 上：

• 染红(1,2)、染蓝(2,3)、染红(2,4)，等价于：节点 2 红，节点 3 蓝，节点 4 红。
• 染蓝(1,2)、染红(2,3)、染蓝(2,4)，等价于：节点 2 蓝，节点 3 红，节点 4 蓝。

这里有一个非常重要的细节：因为每条边对应唯一的非根节点，所以“边染色方案”和“非根节点红点集合”是一一对应的。枚举全部边染色方案，等价于枚举所有非根点的红点集合。

2.3 原约束条件变成点与点之间的局部依赖

原本的条件是：每个点至少有一条红邻边。

现在换成点权视角后，对于一个非根节点u，它的邻边集合由两部分组成：一条父边(parent[u], u)，以及若干条到孩子的边(u, v)。于是：

• 父边是红色，等价于u自己是红点；
• 某条孩子边(u, v)是红色，等价于孩子v是红点。

所以“u的邻边至少一条红”就可以改写成：

u是红点，或者至少存在一个孩子v是红点。

对于根节点，它没有父边，所以只能靠孩子：根必须至少有一个孩子是红点。

这样一变，原本横跨父子两端的边约束，变成了只看点自己和它的孩子的局部约束。树的父子关系天然提供了 DP 的拓扑顺序，边权转点权之后，DP 状态自然就顺了。

2.4 为什么这个转化这么干净

因为“点”是树结构里最小的自治单位。一个点的决策只需要它自己和直接相邻的孩子参与，不需要跨到子树外面。边权转点权之后，红点集合可以直接看作一种“覆盖”：一个红点既能覆盖自己（因为它的父边是红的），也能覆盖它的父节点（因为父节点有一条红邻边了）。

这就是典型的“点覆盖思维”：边上的权值挂到点上，染色问题变成选择红点问题，约束条件变成覆盖条件。比赛里很多看似复杂的边染色题，本质上都是在考这一点。

3. 状态设计：一维DP从直觉到可写代码

3.1 状态定义

边权转点权之后，我重新设计状态，并且这次只用了两个值：

• dp[u][0]：当u是蓝点时，以u为根的子树内部所有点（包括u自己）都已经满足约束的最小代价。
• dp[u][1]：当u是红点时，以u为根的子树内部所有点（包括u自己）都已经满足约束的最小代价。

这里的“蓝点/红点”就是边权转点权之后的节点颜色：“红点”表示u到父节点的边是红色；“蓝点”表示u到父节点的边是蓝色。根节点没有父边，所以不适用“红点”状态，后面会单独处理。

3.2 初始值的直觉

对于非根节点u：

• 如果u选择红点，那么它到父节点的边是红色的，代价至少是这条边的权值w[u]，所以dp[u][1]初始为w[u]。
• 如果u选择蓝点，父边不花钱，所以dp[u][0]初始为 0。

然后我们逐个合并孩子v的子树信息，最终得到完整的dp[u][0]和dp[u][1]。

3.3 为什么这个定义能自洽

关键点在于：dp[u][0/1]在返回给父节点时，已经包含了u自己必须满足的约束条件。

当父节点拿到dp[u][1]时，它知道这条边(parent[u], u)是红的，所以u已经通过父边获得了一条红邻边，u的约束自动满足；子树里其他节点也全部满足。当父节点拿到dp[u][0]时，它知道边(parent[u], u)是蓝的，那么u必须从自己的孩子那里得到红邻边，这个条件在dp[u][0]的转移过程中就已经被强制保证。

所以每个节点向上汇报时，只需要汇报自己的颜色，不需要额外汇报“我是不是已经满足了”，因为满足与否是转移过程中必须完成的事情。

3.4 相比二维状态的优势

我也见过很多人一开始写dp[u][i][j]，第二维表示“u是否已经有一条红邻边”，这本质上是在把一维状态拆开看。写起来问题不大，但容易在初始化、合并时漏掉状态。

一维状态之所以可行，是因为我们在u处自己完成了“至少一个孩子是红点”的强制性判断。这个判断就是 DP 转移里最精彩的一部分，接下来单独讲。

4. 转移方程的完整推导与实现

4.1 先看“u 是红点”的情况

如果u是红点，那么u到父节点的边是红色的，u的“至少一条红邻边”约束已经被父边满足了。

这种情况下，每个孩子v怎么选？v可以是红点，也可以是蓝点，因为我们不需要孩子来给u凑红邻边了。但要注意，v无论选哪个，都必须保证它自己子树内部合法，也就是取：

• v为蓝点时代价是dp[v][0]
• v为红点时代价是dp[v][1]

u对每个孩子都取最小值即可：

dp[u][1] += min(dp[v][0], dp[v][1])

这里为什么不需要管“孩子是否红会不会影响父节点”？因为父节点u已经红了，它不需要孩子贡献红邻边。孩子的颜色只影响孩子自己子树的代价，不影响u的合法性。

4.2 再看“u 是蓝点”的情况

如果u是蓝点，那么它的父边是蓝色的，u不能靠父边获得红邻边。于是它必须至少有一个孩子v是红点，这样边(u, v)才是红的，u才能满足约束。

那怎么求最小代价？一个直观的方法是：先假设所有孩子都选蓝点，这时代价是sum(dp[v][0])。但问题来了，如果所有孩子都选蓝点，u就没有红邻边了，方案非法。我们必须在这些孩子里至少挑一个，把它从蓝点改成红点。

把某个孩子v从蓝点改成红点，需要额外付出的代价是：

gap = dp[v][1] - dp[v][0]

为了让改动最小，我们要在所有孩子里找一个gap最小的，把它强制改成红点。所以：

dp[u][0] = sum(dp[v][0]) + min_gap

前提是u至少有一个孩子。如果u是叶子节点，没有任何孩子，那么蓝点的u没有红邻边，无解，dp[u][0] = INF。

4.3 一个容易被忽略的边界：孩子不能选蓝点时

上面公式成立的前提是：每个孩子的dp[v][0]都是有限值。但实际计算中，如果一个孩子是叶子或者它本身就没办法当蓝点，dp[v][0]会是INF。

比如叶子节点v：dp[v][0] = INF、dp[v][1] = w[v]，也就是说v只能红，不能蓝。在这种情况下，u如果坚持所有孩子先全蓝，就会把INF加进去，答案直接错。

正确的处理办法是：在合并孩子时，如果发现dp[v][0]已经是INF，说明这个孩子必须红，那就直接强制它红，并且u也因此获得了这条红邻边。此时u的“至少一个孩子红”已经满足了，后面的其他孩子可以自由取min(dp[v][0], dp[v][1])。

4.4 完整实现代码

下面是一个直接可用的 C++ 实现，用邻接表存无向树，dfs自底向上合并：

#include <bits/stdc++.h> using namespace std; const long long INF = 4e18; int n; vector<vector<pair<int, long long>>> g; vector<long long> w; // 点权：非根节点对应父边的权值 vector<vector<long long>> dp; void dfs(int u, int fa) { dp[u][0] = 0; dp[u][1] = (fa == 0 ? INF : w[u]); // 根没有父边，不能当红点 bool hasChild = false; // 是否有孩子 bool hasRedChild = false; // 是否已经有一个孩子强制红 long long minGap = INF; // 将孩子从蓝改红的最小增量 for (auto &e : g[u]) { int v = e.first; long long c = e.second; if (v == fa) continue; hasChild = true; w[v] = c; // 边权挂到子端点 dfs(v, u); long long blue = dp[v][0]; long long red = dp[v][1]; // u 是红点：孩子随便选，取 min dp[u][1] += min(blue, red); // u 是蓝点：先尽量让孩子选蓝 if (blue >= INF / 2) { // 孩子 v 不能选蓝，只能红，同时 u 获得一条红邻边 dp[u][0] += red; hasRedChild = true; } else { dp[u][0] += blue; minGap = min(minGap, red - blue); } } if (!hasChild) { // 叶子节点：蓝点无解 dp[u][0] = INF; } else if (!hasRedChild) { // 还没有孩子红，则必须选一个孩子强制改成红点 dp[u][0] += minGap; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n; g.assign(n + 1, {}); w.assign(n + 1, 0); dp.assign(n + 1, vector<long long>(2, 0)); for (int i = 0; i < n - 1; i++) { int u, v; long long c; cin >> u >> v >> c; g[u].push_back({v, c}); g[v].push_back({u, c}); } dfs(1, 0); // 根没有父边，不能是红点，答案只能是 dp[1][0] cout << dp[1][0] << endl; return 0; }

注意dp[1][1]被设为INF，因为根没有父边，不存在“根是红点”这种状态。最后答案取dp[1][0]，含义是：根节点为蓝点，整棵树所有节点都满足约束的最小代价。

4.5 手动演算一个具体例子

用一棵 5 个点的树验证一下：

• 边(1,2)权值 5
• 边(2,3)权值 1
• 边(2,4)权值 2
• 边(4,5)权值 3

根为 1，则各点的点权为：w[2]=5, w[3]=1, w[4]=2, w[5]=3。

叶子节点 3：dp[3][0]=INF, dp[3][1]=1。
叶子节点 5：dp[5][0]=INF, dp[5][1]=3。

节点 4，只有孩子 5。因为 5 只能红，dp[4][0]=3，并且 4 获得红邻边；dp[4][1]=2+3=5。

节点 2，孩子为 3 和 4。dp[2][1]=5+min(1,INF)+min(3,5)=9。
dp[2][0]：孩子 3 只能红，强制红，代价 1，于是2已经有红邻边；孩子 4 选蓝更优，代价 3，所以dp[2][0]=1+3=4。

根节点 1，只有孩子 2。dp[1][0]必须至少一个孩子红，孩子 2 选蓝代价 4、选红代价 9，强制改红的增量为 5，所以答案是4+5=9。

手动检查最优染色：红边(1,2)、(2,3)、(4,5)，蓝边(2,4)，总权值5+1+3=9。每个点的邻边都有红边，正确。

5. 实现细节与调试时的几个坑

5.1 邻接表的建树方式

由于树是无向图，dfs时必须传入父节点参数，避免往回走。树不存在环，所以不需要vis数组，但fa参数是必须的。建图时记得存双向边，一个方向的权值相同。

有人会问：为什么不在读入时直接转成有向图？因为树的根是任选的，你一开始不知道谁是谁的父节点。所以先在无向图上建好邻接表，再通过一次dfs确定父子关系，顺便把边权挂到子节点上。

5.2 叶子节点的dp[u][0]必须为 INF

叶子节点没有孩子，如果它自己是蓝点，它的邻边只有一条父边，而且父边是蓝色，那么它没有任何红邻边，条件不可能满足。所以叶子节点的dp[u][0] = INF。

这一点特别容易出错。很多初学者在写转移时，把dp[u][0]初始化为 0，然后什么也不加，直接返回给父节点，结果叶子节点蓝的时候也变成合法方案了。调试时一定要检查这个边界。

5.3 根节点不能当“红点”

虽然代码里dp[1][1] = INF，但我在第一次实现时偷懒没设，想着反正最后输出dp[1][0]，dp[1][1]不会被用到。结果后来在写换根 DP 的变体时才发现这个隐患——只要还有父节点可能引用dp[u][1]，根的“红点”状态就必须是非法状态。

所以最好在一开始就养成习惯：根节点没有父边，不允许进入dp[root][1]状态。

5.4 INF 的取值与溢出风险

树形 DP 的求和项很多，INF不能设太小，否则真实答案可能超过INF；也不能设成4e18这种接近long long上限的值，因为如果某个dp值本身已经是INF，再加几次可能溢出。

稳妥做法：INF = 4e18配合判断if (blue >= INF / 2)来识别“这个孩子其实不能选蓝”。同时题目如果保证有合法解，那么大多数情况下不会真的出现所有孩子都INF的情况，但写好判断总比溢出后查半天要好。

5.5 对拍验证：暴力枚举是最快的查错方式

我在实现完 DP 后，并没有直接提交，而是写了一个暴力程序对拍。对于n <= 12的随机树，暴力枚举所有2^(n-1)种边染色方案，检查每个点是否满足约束，求出最小红边权值和，然后和树形 DP 的结果对比。

就是这个对拍过程，让我发现了“孩子不能选蓝时会导致dp[u][0]错误累加 INF”的问题。如果你也在做这道题，强烈建议写一个这样的小对拍脚本，几秒钟就能跑几百组随机数据，比自己盯着代码干想要高效得多。

// 暴力对拍核心：枚举每条边红/蓝，检查合法性 // 边编号 0..n-2，用位运算枚举 long long bruteForce() { long long best = INF; int m = n - 1; for (int mask = 0; mask < (1 << m); mask++) { long long cost = 0; // 根据 mask 染色，cost 为红色边权值和 // 检查每个点邻边是否至少一条红 // 若合法，更新 best } return best; }

5.6 递归深度问题

树的n如果到1e5甚至2e5，递归dfs可能会爆栈。比赛环境下不同平台栈大小不一样，稳妥做法是把递归改成显式栈的迭代 DFS，或者提前预估深度并使用带栈扩展的方式。

不过对于练习版，大多数平台上1e5的递归还是能过的。如果发现栈溢出，优先考虑改成迭代后序遍历，思路完全一样，只是把“先递归孩子”换成“先入栈后处理”。

6. 这个模型的推广：方案数、加强约束、换根DP

6.1 求方案数版本

如果题目不是求最小代价，而是问有多少种合法的染色方案，转移思路一模一样，只是把求和变成求积。

对于每个孩子v，它有dp[v][0]和dp[v][1]两种合法子树方案。u为红点时，孩子随便选，方案数为所有孩子(dp[v][0] + dp[v][1])的乘积。

u为蓝点时，不能所有孩子都是蓝点，至少要有一个孩子红。计算方式可以用容斥：先不考虑强制条件，所有孩子任意选的方案数减去所有孩子都选蓝的方案数，即：

dp[u][0] = Π(dp[v][0] + dp[v][1]) - Π(dp[v][0])

这个容斥式的正确性前提是：dp[v][0]代表孩子选蓝且子树合法的方案数。如果遇到dp[v][0] = 0，就相当于这个孩子强制红，容斥公式依然成立，不需要像求最小值那样额外分类。这也能看出求方案数时边权转点权后的建模优势。

6.2 如果要求“每个点至少 k 条红边”

有些变体题目会把“至少一条红边”改成“至少 k 条红边”。这时候一维状态就不够了，需要在u这个维度上再加一个背包维度：

dp[u][j][0/1]

j表示从孩子那边获得了多少条红邻边，第三维表示u是否为红点。每个孩子v如果选红，就会给u贡献 1 条红邻边；如果选蓝，则贡献 0。

合并孩子时做一个背包即可，复杂度从O(n)上升到O(nk^2)，但整体思路还是边权转点权：边的状态挂在孩子上，父节点统计孩子红点的个数。

6.3 和其他经典树上模型的联系

“每个点至少邻接一条红边”本质上是一个最小权的边覆盖问题，但转移到点权后，就变成了一个“树上的强制点覆盖”问题。

如果你熟悉树上点覆盖，会发现转移逻辑高度相似。实际比赛中，这类题经常换一个包装出现在各种题目里，比如传感器覆盖、摄像头放置、半径监控等等。识别出“边权可以下沉到点”这个模式，比背一道题的题解有用得多。

6.4 个人经验

就我个人刷题体验来说，这类题的突破口往往不在 DP 本身的转移难度，而在于最开始用什么“单位”去建模。一旦你能意识到边有两个主人、决策不好局部化，就应该条件反射地想到边权转点权：选一个根，把每条边权沉到子节点上，把边的问题变成点的问题。接下来设计状态、写转移、处理边界，最后对拍验证。

“边的染色”这个题因为状态简单，很适合作为边权重构类题目的入门题。做完之后再去看那些复杂的树上带权覆盖问题，你会发现很多东西都是相通的。先把这一道题吃透，后面的路会顺很多。