33 · 区间 DP 与树形 DP

第 31 节的线性 DP 从左往右扫，第 32 节的背包按容量递增，顺序都由下标决定。这一节的两个结构没有现成的下标顺序可用：区间要从短往长算，树要等儿子算完再算父亲。规矩其实是同一条——递推顺序必须和状态依赖关系一致：依赖谁，就先算谁。

先看清三块骨头：区间 DP 的三层循环、树的存法、树的遍历顺序。前两块是写法，第三块是这一节真正的思想。

#include <bits/stdc++.h>
using namespace std;

int n = 5, a[105], s[105];
int f[105][105];                 // f[l][r]：把 a[l..r] 合并成一堆的最小代价

int main() {
    for (int i = 1; i <= n; ++i) { a[i] = i; s[i] = s[i - 1] + a[i]; }
    memset(f, 0x3f, sizeof f);
    for (int i = 1; i <= n; ++i) f[i][i] = 0;        // 长度 1：本来就是一堆，不需要合并

    for (int len = 2; len <= n; ++len)               // ① 先短后长
        for (int l = 1, r = len; r <= n; ++l, ++r)   // ② 再扫左端点
            for (int k = l; k < r; ++k)              // ③ 最后枚举断点
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);

    cout << f[1][n] << "\n";                         // 1..5 合并的最小代价
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int N = 6005;
vector<int> g[N];                 // 全局：默认全是空表

int main() {
    // 无向树：1-2, 1-3, 3-4，每条边两个方向都要存
    g[1].push_back(2); g[2].push_back(1);
    g[1].push_back(3); g[3].push_back(1);
    g[3].push_back(4); g[4].push_back(3);

    for (int v : g[1]) cout << v << ' ';    // 2 3
    cout << "\n" << g[1].size() << "\n";    // 2
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
vector<int> g[N];
int sz[N], dep[N];

void dfs(int u, int fa) {
    sz[u] = 1;                        // 自己算一个点
    dep[u] = dep[fa] + 1;             // 深度可以顺着参数/父亲递推
    for (int v : g[u]) {
        if (v == fa) continue;        // 父亲方向是来的路
        dfs(v, u);                    // ★ 先递归：等 sz[v] 算完
        sz[u] += sz[v];               // ★ 再合并
    }
}

int main() {
    g[1].push_back(2); g[2].push_back(1);
    g[1].push_back(3); g[3].push_back(1);
    g[3].push_back(4); g[4].push_back(3);
    dep[0] = 0;
    dfs(1, 0);                        // 0 是虚点，编号从 1 起，绝不会撞上
    cout << sz[1] << " " << sz[3] << " " << dep[4] << "\n";   // 4 2 3
}

第一道题是本节的模板：一条链上的合并，加上一个环的处理。先把它彻底做透，第二个例题才有参照物。

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
int n, a[205], s[205];              // a 开两倍：破环成链
int f[205][205], g[205][205];      // f 最小得分，g 最大得分

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) { cin >> a[i]; a[i + n] = a[i]; }   // 复制一份接在后面
    for (int i = 1; i <= 2 * n; ++i) s[i] = s[i - 1] + a[i];          // 前缀和：O(1) 取区间和

    memset(f, 0x3f, sizeof f);     // 求最小：初值要足够大
    memset(g, 0, sizeof g);        // 求最大：得分非负，初值 0 就行
    for (int i = 1; i <= 2 * n; ++i) f[i][i] = g[i][i] = 0;   // 单堆不用合并，得分 0

    for (int len = 2; len <= n; ++len)                 // ① 长度从小到大
        for (int l = 1; l + len - 1 <= 2 * n; ++l) {   // ② 左端点
            int r = l + len - 1;
            for (int k = l; k < r; ++k) {              // ③ 断点：左段 [l,k]，右段 [k+1,r]
                int add = s[r] - s[l - 1];             // 本次合并的得分 = 两段总重
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + add);
                g[l][r] = max(g[l][r], g[l][k] + g[k + 1][r] + add);
            }
        }

    int mn = INF, mx = 0;
    for (int l = 1; l <= n; ++l) {                     // 枚举环的断点 = 长度 n 的每个窗口
        mn = min(mn, f[l][l + n - 1]);
        mx = max(mx, g[l][l + n - 1]);
    }
    cout << mn << "\n" << mx << "\n";
    return 0;
}

第二道题把“区间”换成“子树”。注意这一次没有任何“区间长度”可以枚举，顺序完全由递归调用保证。

#include <bits/stdc++.h>
using namespace std;

int n, r[6005];
vector<int> g[6005];        // g[u]：u 的所有直接下属（有向，父 → 子）
int f[6005][2];             // f[u][0] u 不来；f[u][1] u 来
bool hasFa[6005];           // 用来找根：没有上司的人就是根

void dfs(int u) {
    f[u][1] = r[u];         // u 来：先拿到自己的快乐值
    f[u][0] = 0;            // u 不来：自己贡献 0
    for (int v : g[u]) {    // 有向树，边只从父指向子，不会走回头路
        dfs(v);             // ★ 先把儿子的两个值算出来
        f[u][0] += max(f[v][0], f[v][1]);   // u 不来 → 儿子来不来都行
        f[u][1] += f[v][0];                 // u 来了 → 儿子一定不能来
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> r[i];
    for (int i = 1; i < n; ++i) {
        int l, k;                  // k 是 l 的直接上司
        cin >> l >> k;
        g[k].push_back(l);         // 加边 k → l
        hasFa[l] = true;           // l 有上司，不可能是根
    }

    int root = 1;
    for (int i = 1; i <= n; ++i)
        if (!hasFa[i]) { root = i; break; }   // 入度为 0 的点

    dfs(root);
    cout << max(f[root][0], f[root][1]) << "\n";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int N = 16005;
int n;
long long w[N], f[N], ans = LLONG_MIN;   // f[u]：必须含 u 的连通块最大权值和
vector<int> g[N];

void dfs(int u, int fa) {
    f[u] = w[u];                         // 自己这一份先算上
    for (int v : g[u]) {
        if (v == fa) continue;           // 父亲方向是来的路，跳过
        dfs(v, u);                       // ★ 先递归：等 f[v] 算完
        if (f[v] > 0) f[u] += f[v];      // ★ 负贡献的子树整块剪掉（就是一次修剪）
    }
    ans = max(ans, f[u]);                // 每个点都可能是那一块的最高点
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> w[i];
    for (int i = 1; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);               // 无向树，两个方向都要存
    }

    dfs(1, 0);                           // 0 是虚点，编号从 1 起
    cout << ans << "\n";
    return 0;
}