竞技编程 05-06 树形DP与数位DP

前言

前面的 DP 都是处理线性序列或网格上的问题。这一篇介绍两种特殊的状态设计：

树形 DP——状态定义在树的节点上，按子树到根的顺序递推。04-08 树上问题 里讲的换根 DP 其实就是树形 DP 的一种。这篇会讲更基础的模型：最大独立集、删边方案数。

数位 DP——统计 $1$ 到 $N$ 中满足某种条件的数有多少个。$N$ 可以高达 $10^{18}$，但只要按位分解，状态数只有 $O(\log N \times 状态维度)$。

问题的本质

树形 DP：为什么是”从叶到根”？

树有一个天然的计算顺序：先算完所有子树，再算当前节点。因为子树之间互不干扰（无后效性），每个子树可以独立求解，然后把结果汇总到父节点。

状态通常是 $dp[v][\text{某个维度}]$ = 以 $v$ 为根的子树中，满足某种条件的最优值或方案数。转移时遍历 $v$ 的所有子节点，把子节点的 $dp$ 值合并到 $v$。

数位 DP：为什么可以”逐位处理”？

一个数 $N$ 可以写成十进制序列 $d_k d_{k-1} \ldots d_1 d_0$。数位 DP 的思路是：从高位到低位，逐位决定填什么数字。关键状态是”当前是否已经严格小于 $N$“——如果已经小于，后面的位可以随便填；如果还没小于，就只能填 $\le d_i$ 的数字。

理论 + 代码

树形 DP：最大独立集

给定一棵树，选若干节点，要求相邻节点不能同时被选。求最多选几个节点？

状态：$dp[v][0]$ = 不选节点 $v$ 时，子树 $v$ 中的最大独立集大小；$dp[v][1]$ = 选节点 $v$ 时的最大独立集大小。

转移：

• $dp[v][0] = \sum_{c} \max(dp[c][0], dp[c][1])$（不选 $v$，子节点可选可不选）
• $dp[v][1] = 1 + \sum_{c} dp[c][0]$（选了 $v$，子节点不能选）

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> adj[100009];
int dp[100009][2]; // dp[v][0]=不选v, dp[v][1]=选v

void dfs(int v, int p) {
    dp[v][0] = 0;
    dp[v][1] = 1;                                   // ① 选 v 自身
    for (int c : adj[v]) {
        if (c == p) continue;
        dfs(c, v);
        dp[v][0] += max(dp[c][0], dp[c][1]);         // ② 子节点可选可不选
        dp[v][1] += dp[c][0];                         // ③ 选了 v，子节点不能选
    }
}

int main() {
    int N;
    scanf("%d", &N);
    for (int i = 0; i < N - 1; i++) {
        int a, b; scanf("%d%d", &a, &b);
        adj[a].push_back(b); adj[b].push_back(a);
    }
    dfs(1, 0);
    printf("%d\n", max(dp[1][0], dp[1][1]));
}

逐行解析：

• ① 选了节点 $v$，独立集大小至少 1（$v$ 自身）。
• ② 不选 $v$ 时，每个子节点 $c$ 可以选也可以不选，取较大值累加。
• ③ 选了 $v$ 时，子节点 $c$ 一定不能选，所以只能加 $dp[c][0]$。

数位 DP：统计满足条件的数

统计 $1$ 到 $N$ 中，满足某种条件的数有多少个？

通用框架：

// digit DP 框架
string S = to_string(N); // N 的十进制表示
int len = S.size();
long long dp[len+1][2]; // dp[pos][tight]

// dp[pos][tight] = 处理到第 pos 位时的方案数
// tight = 1 表示前面每一位都和 N 相同，当前位受限
// tight = 0 表示已经比 N 小了，当前位可以填 0~9

状态：$dp[pos][tight]$ = 处理到第 $pos$ 位时的合法方案数。$tight=1$ 表示”还没小于 $N$”，$tight=0$ 表示”已经小于 $N$”。

转移：枚举当前位置填的数字 $d$。如果 $tight=1$，则 $d \le S[pos]$；如果 $tight=0$，则 $d$ 可以是 $0 \sim 9$。新的 $tight$ 取决于是否还”紧贴” $N$。

例题

例题 1：T90 026 — Independent Set on a Tree（★4）

题目：$N$ 个节点的树（$N$ 为偶数）。选出 $N/2$ 个节点，使得没有任何两个相邻节点同时被选。输出任意一个合法方案。

数据范围：$2 \le N \le 10^5$

—— AtCoder Typical 90 026

分析：树一定是二分图——可以把所有节点分成两组（按深度奇偶），同一组内没有相邻节点。所以答案就是深度为偶数的 $N/2$ 个节点，或深度为奇数的 $N/2$ 个节点（取较多的一组）。

不需要真的做 DP，二分图染色即可。

代码：

#include <cstdio>
#include <vector>
using namespace std;

vector<int> adj[100009];
int color[100009]; // 0 或 1

void dfs(int v, int p, int c) {
    color[v] = c;
    for (int u : adj[v])
        if (u != p) dfs(u, v, 1 - c); // ① 交替染色
}

int main() {
    int N;
    scanf("%d", &N);
    for (int i = 0; i < N - 1; i++) {
        int a, b; scanf("%d%d", &a, &b);
        adj[a].push_back(b); adj[b].push_back(a);
    }
    dfs(1, 0, 0); // ② 从根开始染色
    vector<int> g0, g1;
    for (int i = 1; i <= N; i++) {
        if (color[i] == 0) g0.push_back(i);
        else g1.push_back(i);
    }
    // ③ 取较大的一组，输出前 N/2 个
    if (g0.size() >= g1.size()) {
        for (int i = 0; i < N / 2; i++) {
            if (i) printf(" ");
            printf("%d", g0[i]);
        }
    } else {
        for (int i = 0; i < N / 2; i++) {
            if (i) printf(" ");
            printf("%d", g1[i]);
        }
    }
    printf("\n");
}

逐行解析：

• ① DFS 交替染色：父节点染 0，子节点染 1，孙节点染 0……
• ② 从节点 1 开始，染 0。
• ③ 因为树是二分图，两组节点各自内部没有边相连。$N$ 是偶数，两组各至少有 $N/2$ 个。

验证：$N=4$，边 $(1,2), (2,3), (2,4)$。DFS 染色：1→0, 2→1, 3→0, 4→0。组 0 = {1,3,4}（3 个），组 1 = {2}（1 个）。输出组 0 的前 $N/2=2$ 个：1 3。节点 1 和 3 不相邻（1 的邻居是 2，3 的邻居是 2），合法。注意本题是 SPJ（任意合法方案均可）。

---

例题 2：T90 073 — We Need Both a and b（★5，树上删边方案数）

题目：$N$ 个节点的树，每个节点标 ‘a’ 或 ‘b’。删掉 0 条或多条边后，要求每个连通分量都同时包含 ‘a’ 和 ‘b’。求方案数。

数据范围：$2 \le N \le 10^5$

—— AtCoder Typical 90 073

分析：树形 DP + 容斥。

设 $dp[v][0]$ = 子树 $v$ 中，$v$ 所在连通分量只有 a 的方案数；$dp[v][1]$ = 只有 b 的方案数；$dp[v][2]$ = 同时有 a 和 b 的方案数。

对节点 $v$ 和子节点 $c$，考虑边 $(v, c)$：

• 保留边：$c$ 所在连通分量和 $v$ 合并
• 删去边：$c$ 所在连通分量必须已经满足条件（即 $dp[c][2]$）

转移（新 $dp'[v][*]$ 从旧 $dp[v][*]$ 和 $dp[c][*]$ 推导）：

合并时，$v$ 的连通分量和 $c$ 的连通分量组合：

• (只有a) + (只有a) → (只有a)
• (只有b) + (只有b) → (只有b)
• (只有a) + (只有b) → (有ab)
• 任何 + (有ab) → (有ab)

代码：

#include <cstdio>
#include <vector>
using namespace std;

const int MOD = 1000000007;
vector<int> adj[100009];
char c[100009];
long long dp[100009][3]; // 0=only_a, 1=only_b, 2=both

void dfs(int v, int p) {
    if (c[v] == 'a') { dp[v][0] = 1; dp[v][1] = 0; }
    else { dp[v][0] = 0; dp[v][1] = 1; } // ① 初始
    dp[v][2] = 0;

    for (int u : adj[v]) {
        if (u == p) continue;
        dfs(u, v);
        long long n0 = (dp[v][0] * dp[u][0] + dp[v][0] * dp[u][2]) % MOD; // ② 保留a+a 或 删边
        long long n1 = (dp[v][1] * dp[u][1] + dp[v][1] * dp[u][2]) % MOD; // ③ 保留b+b 或 删边
        long long n2 = (dp[v][2] * (dp[u][0] + dp[u][1]) % MOD        // ④ 保留: ab+a 或 ab+b
                      + dp[v][2] * dp[u][2] % MOD                      // ④ 保留: ab+ab
                      + dp[v][2] * dp[u][2] % MOD                      // ④ 删边: 各自合法
                      + dp[v][0] * dp[u][1] % MOD                      // ⑤ 保留: a+b→ab
                      + dp[v][1] * dp[u][0] % MOD                      // ⑥ 保留: b+a→ab
                      + dp[v][0] * dp[u][2] % MOD                      // ⑦ 保留: a+ab→ab
                      + dp[v][1] * dp[u][2] % MOD                      // ⑦ 保留: b+ab→ab
                      ) % MOD;
        dp[v][0] = n0;
        dp[v][1] = n1;
        dp[v][2] = n2;
    }
}

int main() {
    int N;
    scanf("%d", &N);
    for (int i = 1; i <= N; i++) {
        char ch; scanf(" %c", &ch); c[i] = ch;
    }
    for (int i = 0; i < N - 1; i++) {
        int a, b; scanf("%d%d", &a, &b);
        adj[a].push_back(b); adj[b].push_back(a);
    }
    dfs(1, 0);
    printf("%lld\n", dp[1][2]); // ⑦ 根节点的"有ab"方案数
}

逐行解析：

• ① 叶节点初始化：如果 $v$ 是 ‘a’，dp[v][0]=1；如果是 ‘b’，dp[v][1]=1。dp[v][2]=0（单个节点不可能同时有 ab）。
• ② 保留边 + $u$ 只有 a：$v$ 的连通分量仍只有 a。$u$ 的”有ab”情况也可以保留（合并后 $v$ 仍只有 a，因为 $u$ 那边没有 b）。
• ⑤⑥ 关键：$v$ 的连通分量只有 a，$u$ 的只有 b，合并后变成”有 ab”。
• ⑦ 答案是根节点”有 ab”的方案数。

---

例题 3：T90 082 — Counting Numbers（★3，按位数分段求和）

题目：$\sum_{x=L}^{R} x \times (\text{十进制位数 of } x)$。$L, R \le 10^{18}$。答案对 $10^9+7$ 取模。

—— AtCoder Typical 90 082

分析：不需要严格的数位 DP。按位数分段：1 位数（1-9），2 位数（10-99），3 位数（100-999），……对每一段，$\sum_{x=l}^{r} x = (l+r)(r-l+1)/2$，乘以位数即可。

代码：

#include <cstdio>
#include <algorithm>
using namespace std;

const long long MOD = 1000000007;

long long solve(long long N) {
    if (N <= 0) return 0;
    long long ans = 0;
    long long p10 = 1; // 10^k（当前位数的起点）
    for (int d = 1; p10 <= N; d++) { // d = 位数
        long long lo = p10;              // ① 当前段最小值
        long long hi = min(N, p10 * 10 - 1); // ② 当前段最大值
        long long cnt = (hi - lo + 1) % MOD; // ③ 这个段有几个数
        long long sum = ((lo + hi) % MOD) * cnt % MOD * ((MOD + 1) / 2) % MOD; // ④ 等差数列求和
        ans = (ans + sum % MOD * d % MOD) % MOD; // ⑤ 乘以位数
        p10 *= 10;
    }
    return ans;
}

int main() {
    long long L, R;
    scanf("%lld%lld", &L, &R);
    long long ans = (solve(R) - solve(L - 1) % MOD + MOD) % MOD; // ⑥ 前缀和相减
    printf("%lld\n", ans);
}

逐行解析：

• ①② 当前位数的段从 $10^{d-1}$ 到 $\min(N, 10^d - 1)$。比如 3 位数从 100 到 $\min(N, 999)$。
• ④ 等差数列求和 $(l+r)(r-l+1)/2$。除以 2 用乘以逆元 $(MOD+1)/2 = 5 \times 10^8 + 4$。
• ⑤ 每个数贡献的字符数 = 数字本身 × 位数。这里 sum 是数字之和，乘以位数 $d$。
• ⑥ $\sum_{L}^{R} = \sum_1^R - \sum_1^{L-1}$。

验证：$L=3, R=5$。

solve(5)：1 位数段 lo=1, hi=5, sum=(1+5)*5/2=15, 乘以 1 = 15。 solve(2)：sum=(1+2)*2/2=3, 乘以 1 = 3。 答案 = 15 - 3 = 12。✓（3+3+3+4+4+4+4+5+5+5+5+5 = 12 个字符。）

---

例题 4：T90 005 — Restricted Digits（★7，DP 倍增）

题目：用数字 $c_1, c_2, \ldots, c_K$ 构造 $N$ 位正整数，其中是 $B$ 的倍数的有多少个？答案对 $10^9+7$ 取模。

数据范围：$1 \le N \le 10^{18}$，$2 \le B \le 1000$，$1 \le K \le 9$

—— AtCoder Typical 90 005

分析：$N \le 10^{18}$ 无法逐位 DP。核心思想是DP 倍增：如果知道「$k$ 位数的余数分布 $dp_k$」和「$10^k \bmod B$」，就能推出「$2k$ 位数的余数分布」：

$dp_{2k}[j] = \sum_{i=0}^{B-1} dp_k[i] \cdot dp_k\left[(j - i \cdot 10^k) \bmod B\right]$

这就是两个长度 $B$ 的向量的「卷积」，每次 $O(B^2)$，总共 $O(B^2 \log N)$，对于 $B=1000$ 约需 $6 \times 10^7$ 次运算。

代码：

#include <cstdio>
#include <cstring>
using namespace std;
const int MOD = 1000000007;
typedef long long ll;

int B;
// ① 合并两个「等长」的余数分布：fa = k 位, fb = k 位, 10^k mod B = p10
// 结果 = 2k 位的余数分布
void merge(ll* fa, ll* fb, ll p10) {
    ll res[1000] = {};
    for (int i = 0; i < B; i++)
        for (int j = 0; j < B; j++)                     // ② 枚举两段的余数
            res[(i * p10 + j) % B] = (res[(i * p10 + j) % B] + fa[i] * fb[j]) % MOD;
    memcpy(fa, res, sizeof(ll) * B);
}

int main() {
    ll N; int K;
    scanf("%lld%d%d", &N, &B, &K);                     // ③ N 位数, 模 B, K 个可用数字
    int C[11];
    for (int i = 0; i < K; i++) scanf("%d", &C[i]);

    // ④ 初始：1 位数的余数分布
    ll dp[1000] = {};
    for (int i = 0; i < K; i++) dp[C[i] % B]++;

    // ⑤ 倍增法：逐位扫描 N 的二进制
    ll cur[1000];                                     // cur = 「1 位的余数分布」
    memcpy(cur, dp, sizeof(ll) * B);
    ll p10 = 10 % B;                                  // 10^1 mod B

    ll n = N - 1;                                     // 需要 N-1 次转移
    while (n > 0) {
        if (n & 1) merge(dp, cur, p10);              // ⑥ 把 cur 接到 dp 后面
        merge(cur, cur, p10);                         // ⑦ cur 翻倍（2k 位）
        p10 = p10 * p10 % B;                          // ⑧ 10^(2k) mod B
        n >>= 1;
    }
    printf("%lld\n", dp[0]);                          // ⑨ 余数为 0 的方案数
}

逐行解析：

• ①② merge：把两个 $k$ 位的余数分布合并成 $2k$ 位的。前面那段乘以 $10^k$ 后移位，加上后面那段，$O(B^2)$。
• ④ 初始状态：每个可用数字 $C[i]$ 贡献到余数 $C[i] \bmod B$。
• ⑤⑥⑦⑧ 倍增主体。cur 表示「$2^t$ 位的余数分布」，p10 = $10^{2^t} \bmod B$。如果 $N-1$ 的第 $t$ 位是 1，就把 cur 接到 dp 后面。
• ⑨ 答案是余数为 0 的方案数。

参考文献

实战练习 — 競プロ典型 90 問

• 026 Independent Set on a Tree（★4，树的最大独立集 = 二分染色）【例题】
• 073 We Need Both a and b（★5，树上删边方案数）【例题】
• 082 Counting Numbers（★3，按位数分段求和）【例题】
• 005 Restricted Digits（★7，数位 DP 模板）【例题】

---

系列索引

第零章 基础工具

• 00-01 复杂度与暴力枚举
• 00-02 排序
• 00-03 累积和与差分

第一章 搜索技术

• 01-01 二分搜索
• 01-02 双指针与尺取法

第二章 数学基础

• 02-01 整数与整除
• 02-02 素数与筛法
• 02-03 同余与模运算
• 02-04 快速幂与逆元
• 02-05 组合计数
• 02-06 容斥原理
• 02-07 欧拉函数
• 02-08 博弈论基础

第三章 数据结构

• 03-01 栈、队列与单调栈
• 03-02 堆与优先队列
• 03-03 并查集
• 03-04 树状数组
• 03-05 线段树
• 03-06 懒标记线段树
• 03-07 Sparse Table 与倍增
• 03-08 字符串哈希

第四章 图论

• 04-01 图的遍历
• 04-02 最短路—Dijkstra 与 01-BFS
• 04-03 最短路—Bellman-Ford 与 Floyd
• 04-04 拓扑排序
• 04-05 最小生成树
• 04-06 强连通分量与 2-SAT
• 04-07 二分图与网络流
• 04-08 树上问题

第五章 动态规划

• 05-01 DP入门—状态与转移
• 05-02 背包问题族
• 05-03 LIS、LCS与编辑距离
• 05-04 区间DP
• 05-05 状态压缩DP
• 05-06 树形DP与数位DP
• 05-07 矩阵快速幂与线性递推

第六章 贪心

• 06-01 贪心策略与交换论证
• 06-02 区间调度与优化

第七章 字符串

• 07-01 字符串哈希详述
• 07-02 后缀数组

第八章 进阶

• 08-01 卷积与FFT
• 08-02 期望与概率
• 08-03 Zeta / Möbius 变换
• 08-04 计算几何基础
• 08-05 采样与随机化