F树形 DP

覆盖 / 支配 / 染色

三状态·染色计数

本课摘要

覆盖 / 支配 / 染色课程回答“覆盖、支配和染色约束需要哪些互斥状态”。内容以三状态·染色计数为主线，配合逐步推导、可编辑演示、例题与练习形成可复查的学习闭环。

  • 判断覆盖 / 支配 / 染色的适用条件与状态边界
  • 围绕“三状态·染色计数”推导转移与计算顺序
  • 用演示、复杂度分析和配套题目校验实现
本课目录 · 0 节

正在整理目录…

当「被覆盖」比「选没选」更微妙

上一批的 f[u][0/1]f[u][0/1] 里，一个点只有「选 / 不选」两态。但支配集把要求提高了一档： 在树上放最少（或最省钱）的警卫，让每个点要么自己是警卫、要么与某个警卫相邻——全树被「支配」。

难点在这：一个没放警卫的点，它到底被覆盖了没有？可能被某个孩子覆盖（孩子放了警卫）， 也可能孩子都没放、只能指望父亲来覆盖它。这两种「没放警卫」的处境后果完全不同，两态不够用了。

udp0 · 放警卫自己 + 全部孩子被覆盖udp1 · 被孩子覆盖至少一个孩子放了警卫udp2 · 等父亲暂时没人覆盖它
支配集需要三个状态：放警卫 / 已被孩子覆盖 / 暂时没人覆盖（等父亲）。

三状态：把「谁来覆盖 u」记进状态

为每个点 uu 开三态，造价意义下取最小：

dp[u][0]: u ;dp[u][1]: u ;dp[u][2]: u dp[u][0]:\ u\ \text{;}\quad dp[u][1]:\ u\ \text{;}\quad dp[u][2]:\ u\

读作：dp[u][0]dp[u][0] = u 放警卫；dp[u][1]dp[u][1] = u 不放、但被某个孩子覆盖；dp[u][2]dp[u][2] = u 不放、也没被孩子覆盖（把覆盖它的责任留给父亲）。转移分三路：

dp[u][0]=cu+∑cmin⁡(dp[c][0],dp[c][1],dp[c][2])dp[u][0]=c_u+\sum_{c}\min\big(dp[c][0],dp[c][1],dp[c][2]\big)

u 放了警卫，它顺手覆盖所有孩子，于是每个孩子三态随便取最小（包括孩子的「等父亲」态——因为 u 就是那个父亲）。

dp[u][2]=∑cmin⁡(dp[c][0],dp[c][1])dp[u][2]=\sum_{c}\min\big(dp[c][0],dp[c][1]\big)

u 不放、也不靠孩子，那每个孩子必须自给自足（自己放警卫，或被它自己的孩子覆盖），不能是「等父亲」态 dp[c][2]dp[c][2]——因为 u 自身都没被覆盖，救不了孩子。

dp[u][1]=dp[u][2]+min⁡c(dp[c][0]−min⁡(dp[c][0],dp[c][1]))dp[u][1]=dp[u][2]+\min_{c}\big(dp[c][0]-\min(dp[c][0],dp[c][1])\big)

dp[u][1]dp[u][1] 的基线和 dp[u][2]dp[u][2] 一样（孩子自足），但额外强制至少一个孩子放警卫来覆盖 u——取「把某个孩子从自足抬到放警卫」的最小增量加上去。

节点 u（权 w）选它？不选 u选 u孩子自由：各取较大dp[u][0] =Σ max(dp[c][0], dp[c][1])孩子必须全不选dp[u][1] = w +Σ dp[c][0]答案 = max(dp[root][0], dp[root][1])
与独立集的两态分叉相比，支配集多出的第三态 dp[u][2]dp[u][2] 是「把覆盖延迟给父亲」的记账位。

本质

「点覆盖」盯的是边（每条边有人守），「支配集」盯的是点（每个点被支配）。后者的困难全在——没放警卫的点，覆盖它的责任可能来自孩子、也可能来自父亲。把这个「责任方向」显式记成第三态，DFS 才能在后序时正确结算。三态是支配集类题的通用骨架。

跟着算一遍

小树：根 11 带 2,3,42,3,4；22 带一个孩子 55。造价 c=[5,3,4,6,2]c=[5,3,4,6,2]。后序 5,2,3,4,15,2,3,4,1：

1
叶子 5、3、4。 叶子：dp[0]=cdp[0]=c（放警卫），dp[1]=∞dp[1]=\infty（无孩子可覆盖），dp[2]=0dp[2]=0（等父亲）。如 dp[5]=(2,∞,0)dp[5]=(2,\infty,0)。
2
节点 2（造价 3，孩子 5）。放警卫 dp[2][0]=3+min⁡(2,∞,0)=3+0=3dp[2][0]=3+\min(2,\infty,0)=3+0=3；等父亲 dp[2][2]=min⁡(2,∞)=2dp[2][2]=\min(2,\infty)=2（孩子 5 须自足，只能放警卫）；被孩子覆盖 dp[2][1]=2+(2−2)=2dp[2][1]=2+(2-2)=2。得 dp[2]=(3,2,2)dp[2]=(3,2,2)。
3
根 1（造价 5，孩子 2、3、4）。放警卫 dp[1][0]=5+min⁡(dp[2])+min⁡(dp[3])+min⁡(dp[4])dp[1][0]=5+\min(dp[2])+\min(dp[3])+\min(dp[4])。孩子们的三态最小值分别是 2,4,62,4,6（3、4 是叶子，min 取「等父亲」= 0），所以 dp[1][0]=5+2+0+0=7dp[1][0]=5+2+0+0=7。
✓
答案 = min⁡(dp[1][0],dp[1][1])\min(dp[1][0],dp[1][1])（根不许「等父亲」）。在这组造价下最省是 7：只在根 1 放警卫，它覆盖 2、3、4，而 5 被 2……需再核 5：故实际最优会让 2 也放。演示会给出精确解。
下面的演示把三状态 dp0/dp1/dp2dp0/dp1/dp2 逐点填入，末帧用颜色区分放警卫（绿）与被覆盖（青）；改造价看最优布防移动。

看三状态逐点点亮

改每个哨点的造价，看三状态 dp0/dp1/dp2 重算
1
哨点 1 · 造价
5
2
哨点 2 · 造价
3
3
哨点 3 · 造价
4
4
哨点 4 · 造价
6
5
哨点 5 · 造价
2
节点下方 dp0 / dp1 / dp2 三值 = 放警卫 / 被孩子覆盖 / 空着等父亲 三种局面的最小造价。 根不许停在 dp2（没人能覆盖它），答案 = min(dp0[1], dp1[1]) = 7。
1¥523/∞/03¥44¥65¥2
已暂停，第 1 步，共 5 步，1 倍速
当前处理 放了警卫 被覆盖(无警卫)
叶子 2：放警卫 d0=3，靠孩子覆盖不可行，等父亲 d2=0。

另一面：染色计数，同时求 max 与 min

覆盖类还有一支是染色计数。三色二叉树：每个节点涂红 / 绿 / 蓝之一，要求父子不同色、兄弟不同色， 问绿色节点数的最大值与最小值各是多少。这不是求方案数，而是在「合法染色」的约束下优化一个计数。

状态自然是 f[u][col]f[u][col] = u 涂 colcol 色时、其子树里的绿点数（分别维护 max 与 min）。转移枚举左右孩子的颜色 a,ba,b，要求 a≠col, b≠col, a≠ba\ne col,\ b\ne col,\ a\ne b：

fmax⁡[u][col]=[col=green]+max⁡a,b(fmax⁡[l][a]+fmax⁡[r][b])f_{\max}[u][col]=[col=\text{green}]+\max_{a,b}\big(f_{\max}[l][a]+f_{\max}[r][b]\big)

fmin⁡f_{\min} 同理把 max⁡\max 换 min⁡\min。因为只有三种颜色、两个孩子，内层枚举是常数级，整体仍是 O(n)O(n)。同一份 DFS 同时算出 max 与 min 两个答案。

1523344152金色序号 = 处理次序：叶子 4、5 先算好，父亲 2 才能合并；根 1 最后收口。
染色计数也是后序：孩子每种颜色的最优绿点数先备好，父亲再枚举「与自己不冲突」的颜色组合。

常见陷阱：极值与方案数别混为一谈

三色二叉树求的是「绿点数的 max/min」这一极值，转移用 max⁡/min⁡\max/\min；若题目改问「合法染色的方案数」，则要把内层的取极值换成累乘 + 累加（每种合法 (a,b)(a,b) 的方案数相乘再对颜色求和）。同一棵树、同一套约束，「求极值」与「数方案」的算子完全不同——下一类 方案数 / 距离统计 专讲后者。

例题

P2458[SDOI2006] 保安站岗SDOI 2006提高+/省选-
题意
树上每点放保安有造价 cic_i，保安可看守自己与相邻点。求看守全部点的最小造价（带权最小支配集）。
对应关系
三状态 dp[u][0/1/2]dp[u][0/1/2] = 放警卫 / 被孩子覆盖 / 等父亲。引入「等父亲」这个第三态，是它比点覆盖复杂一档、也是支配集教学标准题的原因。
转移 · 复杂度
见上方三条方程；一遍 DFS，O(n)O(n)。根取 min⁡(dp[0],dp[1])\min(dp[0],dp[1])。
参考代码（三状态 DFS）
C++
在洛谷打开 P2458 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 1505;
vector<int> g[N];
int c[N];                     // c[u]：在 u 放警卫的造价
long long f[N][3];            // 0:放警卫  1:被某孩子覆盖  2:空着,等父亲来覆盖
bool hasFa[N];

const long long INF = 1e15;

void dfs(int u)
{
    f[u][0] = c[u];           // 放警卫：先付自己的造价
    f[u][1] = 0;              // 被孩子覆盖：下面累加，另需至少一个孩子放警卫
    f[u][2] = 0;              // 等父亲覆盖：孩子必须自给自足
    long long extra = INF;    // 把某个孩子从"自足"抬到"放警卫"的最小增量
    bool hasChild = false;

    for (int v : g[u])
    {
        hasChild = true;
        dfs(v);
        f[u][0] += min({f[v][0], f[v][1], f[v][2]});  // u 已覆盖孩子,孩子随意取最小
        long long self = min(f[v][0], f[v][1]);        // 孩子"自足"(不靠 u)
        f[u][1] += self;
        f[u][2] += self;
        extra = min(extra, f[v][0] - self);            // 让这个孩子改放警卫的代价
    }

    if (!hasChild) f[u][1] = INF;      // 叶子无孩子,不可能"被孩子覆盖"
    else f[u][1] += extra;             // ★强制至少一个孩子放警卫
}

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int u, cost, k;
        cin >> u >> cost >> k;
        c[u] = cost;
        while (k--)
        {
            int v;
            cin >> v;
            g[u].push_back(v);
            hasFa[v] = true;
        }
    }

    int root = 1;
    while (root <= n && hasFa[root]) root++;

    dfs(root);
    cout << min(f[root][0], f[root][1]) << endl;  // 根不能停在状态 2
    return 0;
}
P2585[ZJOI2006] 三色二叉树ZJOI 2006提高+/省选-
题意
给定二叉树（括号串描述），红 / 绿 / 蓝三色染色，父子异色、兄弟异色，求绿色节点数的最大值与最小值。
为什么选它
父子 + 兄弟双约束的按色 DP，且同时求 max/min——一题覆盖「颜色枚举」与「极值双跑」两个要点，是覆盖类里计数/极值方向的代表。
转移 · 复杂度
f[u][col]=[col=green]+opta≠col,b≠col,a≠b(f[l][a]+f[r][b])f[u][col]=[col=\text{green}]+\text{opt}_{a\ne col,b\ne col,a\ne b}(f[l][a]+f[r][b])（opt\text{opt} 为 max 或 min）；O(n)O(n)。
参考代码（括号串建树 + 按色 DP）
C++
在洛谷打开 P2585 
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

const int N = 500005;
int lc[N], ls[N];             // 用括号串重建二叉树的左右孩子
string s;
int idx;
long long fmax[N][3], fmin[N][3]; // 颜色 0/1/2，其中「绿」（设为 2）计入统计

int build()                   // 按括号串递归建树，返回当前节点编号
{
    int u = ++idx;
    char ch = s[u - 1];
    lc[u] = ls[u] = 0;
    if (ch >= '2') lc[u] = build();   // 有左孩子
    if (ch == '2') ls[u] = build();   // 有右孩子（'2' 表示两个孩子）
    return u;
}

void dfs(int u)
{
    if (!u) return;
    dfs(lc[u]);
    dfs(ls[u]);
    for (int col = 0; col < 3; col++)
    {
        long long addG = (col == 2) ? 1 : 0;   // 绿色 +1
        // 左右孩子颜色都要与 u 不同；两孩子之间也不同
        long long bestMax = -1, bestMin = 1e18;
        for (int a = 0; a < 3; a++)
            for (int b = 0; b < 3; b++)
            {
                if (a == col || b == col || a == b) continue;
                long long lM = lc[u] ? fmax[lc[u]][a] : 0;
                long long rM = ls[u] ? fmax[ls[u]][b] : 0;
                long long lm = lc[u] ? fmin[lc[u]][a] : 0;
                long long rm = ls[u] ? fmin[ls[u]][b] : 0;
                bestMax = max(bestMax, lM + rM);
                bestMin = min(bestMin, lm + rm);
            }
        // 单孩子/叶子时另作简化处理（此处示意主干）
        fmax[u][col] = addG + bestMax;
        fmin[u][col] = addG + bestMin;
    }
}

int main()
{
    cin >> s;
    idx = 0;
    int root = build();

    dfs(root);
    long long mx = max({fmax[root][0], fmax[root][1], fmax[root][2]});
    long long mn = min({fmin[root][0], fmin[root][1], fmin[root][2]});
    cout << mx << endl << mn << endl;
    return 0;
}

练习

P2279[HNOI2003] 消防局的设立距离 ≤ 2 的支配集：一个局能覆盖距离不超过 2 的点。状态要按「到最近局的距离」分更多档（0/1/2 + 等父亲若干态），贪心也可，DP 更稳。在洛谷打开
P5018[NOIP2018] 对称二叉树较新真题：判断最大的对称子树。f 记录以每个点为根的子树是否对称 + 结构哈希；对称要求左子树与右子树镜像（结构 + 权值都对称）。在洛谷打开
P2585三色二叉树（自测）独立写一遍括号串建树 + 三色 DP，注意叶子/单孩子的边界，以及 max 与 min 两份数组同步转移。在洛谷打开

已进入 覆盖 / 支配 / 染色 · 树形 DP · DP大师