Content：DP (Interval, Tree)
Date：2025.7.24

概览

  • 区间 DP
  • 树形 DP

例题

洛谷-P4516 潜入行动

题目大意

题目大意

给定一颗树，要求在树上选取恰好 k\large k 个节点 (不得重复)，每个选取的节点可以覆盖它的邻居，但是不能覆盖自己本身。要求选取的这 k\large k 个节点覆盖所有的 n\large n 个节点。求方案数。
数据范围 n≤105,k≤100\large n \le 10^5, k \le 100。

思路

我们考虑树形动态规划。定义状态 fu,i,0/1,0/1\large f_{u,i,0/1,0/1} 表示以 u\large u 为根的子树内，选取了 i\large i 个节点，其中点 u\large u 放了/不放，被/不被覆盖的方案数。初始状态为：

fu,0,0,0=1fu,1,1,0=1\large \begin{aligned} f_{u,0,0,0} = 1 \\ f_{u,1,1,0} = 1 \\ \end{aligned}

可以发现如果只看前两维的话，是一个典型的树形背包问题。接下来我们考虑加上后两维后如何转移 (本质还是树形背包)。

  1. 对于 fu,i,0,0\large f_{u,i,0,0}，即点 u\large u 既不选择，也 不覆盖，所以 uu 的子节点 vv 一定不能选择，而 vv 必须 覆盖，所以其转移如下：

    fu,i,0,0=∑v∈son⁡(u)fu,i−j,0,0×fv,j,0,1 \large f_{u,i,0,0} = \sum_{v \in \operatorname{son}(u)} f_{u,i - j,0,0} \times f_{v,j,0,1}

  2. 对于 fu,i,0,1\large f_{u,i,0,1}，即点 u\large u 不选择，但是被覆盖。因为状态为点 uu 被覆盖，所以既可以是 vv 覆盖的，也可能是 uu 的其他子节点覆盖的，而因为 uu 不被选择，所以 vv 一定是已经被覆盖了的，所以其转移如下：

    fu,i,0,1=∑v∈son⁡(u)fu,i−j,0,1×(fv,j,0,1+fv,j,1,1)+∑v∈son⁡(u)fu,i−j,0,0×fv,j,1,1 \large f_{u,i,0,1} = \sum_{v \in \operatorname{son}(u)} f_{u,i-j,0,1} \times (f_{v,j,0,1} + f_{v,j,1,1}) + \sum_{v \in \operatorname{son}(u)} f_{u,i-j,0,0} \times f_{v,j,1,1}

  3. 对于 fu,i,1,0\large f_{u,i,1,0}，即点 u\large u 选择了，但还没有被覆盖。因为不被覆盖，所以点 v\large v 一定不能被选择，而点 u\large u 已经被选择了，所以点 v\large v 覆不覆盖无所谓。转移如下：

    fu,i,1,0=∑v∈son⁡(u)fu,i−j,1,0×(fv,j,0,1+fv,j,0,0) \large f_{u,i,1,0} = \sum_{v \in \operatorname{son}(u)} f_{u,i-j,1,0} \times (f_{v,j,0,1} + f_{v,j,0,0})

  4. 对于 fu,i,1,1\large f_{u,i,1,1}，即点 u\large u 选择了，也被覆盖了的情况。由 1,31,3 两种情况类似的推导就可以得到。转移为：

    fu,i,1,1=∑v∈son⁡(u)fu,i−j,1,1×(fv,j,0,0+fv,j,0,1+fv,j,1,0+fv,j,1,1)+∑v∈son⁡(u)fu,i−j,1,0×(fv,j,1,0+fv,j,1,1) \large f_{u,i,1,1} = \sum_{v \in \operatorname{son}(u)} f_{u,i-j,1,1} \times (f_{v,j,0,0} + f_{v,j,0,1} + f_{v,j,1,0} + f_{v,j,1,1}) + \sum_{v \in \operatorname{son}(u)} f_{u,i-j,1,0} \times (f_{v,j,1,0} + f_{v,j,1,1})

最后，注意 取模 和 long long!!!

Code

Code

#include <bits/stdc++.h>

namespace IO {
    template<typename name> name read() {
        name x = 0, f = 1; char ch = getchar();
        while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
        while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
        return x * f;
    }
    template<typename name> void _write(name x) {
        if (x > 9) _write(x / 10);
        putchar(x % 10 + '0');
    }
    template<typename name> void write(name x) {
        if (x < 0) putchar('-'), x = -x;
        _write(x);
    }
}

constexpr int N = 1e5 + 5, K = 105, MOD = 1e9 + 7;
int head[N], next[N << 1], to[N << 1], cnt = 0;
int dp[N][K][2][2], size[N], tmp[K][2][2];
int n, k, u, v;

inline void AddEdge(const int u, const int v) {
    to[cnt] = v;
    next[cnt] = head[u];
    head[u] = cnt++;
}

inline void Dfs(int u, int father) {
    dp[u][0][0][0] = dp[u][1][1][0] = 1;
    size[u] = 1;
    
    for (int i = head[u]; ~i; i = next[i]) {
        const int v = to[i];
        if (v == father) continue;
        
        Dfs(v, u);
        size[u] += size[v];
        
        // ! 这里要进行备份，不然转移的时候会出现问题（用已修改的状态修改未修改的状态）
        for (int t = 0; t <= std::min(k, size[u]); t++) {
            tmp[t][0][0] = dp[u][t][0][0];
            tmp[t][1][0] = dp[u][t][1][0];
            tmp[t][0][1] = dp[u][t][0][1];
            tmp[t][1][1] = dp[u][t][1][1];
            dp[u][t][0][0] = dp[u][t][1][0] = dp[u][t][0][1] = dp[u][t][1][1] = 0;
        }
        
        // ! 注意枚举范围，不能直接枚举区间 [0,k]，不然会 TLE
        for (int t = 0; t <= std::min(size[u], k); t++) {
            // ! 这里同理
            for (int j = 0; j <= std::min(size[v], t); j++) {
                if (t - j > size[u] - size[v]) continue;
                
                // // 可恶的转移
                (dp[u][t][0][0] += (long long) tmp[t - j][0][0] * dp[v][j][0][1] % MOD) %= MOD;
                (dp[u][t][0][1] += ((long long) tmp[t - j][0][1] * ((dp[v][j][0][1] + dp[v][j][1][1]) % MOD) % MOD + (long long) tmp[t - j][0][0] * dp[v][j][1][1] % MOD) % MOD) %= MOD;
                (dp[u][t][1][0] += (long long) tmp[t - j][1][0] * ((dp[v][j][0][1] + dp[v][j][0][0]) % MOD) % MOD) %= MOD;
                (dp[u][t][1][1] += ((long long) (tmp[t - j][1][1] * (((long long) dp[v][j][0][1] + dp[v][j][0][0] + dp[v][j][1][0] + dp[v][j][1][1]) % MOD) % MOD) + (long long) tmp[t - j][1][0] * ((dp[v][j][1][1] + dp[v][j][1][0]) % MOD) % MOD) % MOD) %= MOD;
            }
        }
    }
}

int main() {
    using namespace IO;
    
    n = read<int>();
    k = read<int>();
    
    for (int i = 1; i <= n; i++) head[i] = -1;
    
    for (int i = 1; i < n; i++) {
        u = read<int>(), v = read<int>();
        AddEdge(u, v);
        AddEdge(v, u);
    }
    
    Dfs(1, 1);
    
    write((1ll * dp[1][k][0][1] + dp[1][k][1][1]) % MOD);
    
    return 0;
}

洛谷-P1352 没有上司的舞会 (经典题)

题目大意

题目大意

给定一颗有 nn 个节点的树，表示员工的架构，现在有一个舞会需要举办，你要选取一些人参加，第 i\large i 个人参加可以为舞会带来 ri\large r_i 的快乐值，但是如果第 i\large i 个人的直接上司 (i\large i 的父亲节点) 参加了，那么 i\large i 就不会参加，你要最大化选择的人的快乐值之和。
数据范围：n≤6×103\large n \le 6 \times 10^3。

思路

定义状态 fu,0/1\large f_{u,0/1} 表示节点 u\large u 参加/不参加能为舞会带来的最大价值。

转移如下：

fu,0=∑v∈son⁡(u)max⁡(fv,0,fv,1)fu,1=∑v∈son⁡(u)fv,0+ri\large \begin{aligned} f_{u,0} &= \sum_{v \in \operatorname{son}(u)} \max(f_{v,0}, f_{v,1}) \\ f_{u,1} &= \sum_{v \in \operatorname{son}(u)} f_{v,0} + r_i \end{aligned}

注意我的树存的是双向边，和边有关的数组要开 2\large 2 倍。

Code

Code

#include <bits/stdc++.h>

using std::cin;
using std::cout;

constexpr int MAXN = 6e4 + 5;
int head[MAXN], to[MAXN], next[MAXN], cnt = 0;
int n, r[MAXN], u, v;
int dp[MAXN][2];

void add_edge(const int u, const int v) {
    to[cnt] = v;
    next[cnt] = head[u];
    head[u] = cnt++;
}

void dfs(const int u, const int father) {
    dp[u][1] = r[u];
    
    for (int i = head[u]; ~i; i = next[i]) {
        const int v = to[i];
        if (v == father) continue;
        
        dfs(v, u);
        dp[u][0] += std::max(dp[v][0], dp[v][1]);
        dp[u][1] += dp[v][0];
    }
}

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

    std::memset(head, -1, sizeof(head));
    
    cin >> n;
    
    for (int i = 1; i <= n; i++) {
        cin >> r[i];
    }
    
    for (int i = 1; i < n; i++) {
        cin >> u >> v;
        add_edge(u, v);
        add_edge(v, u);
    }
    
    dfs(1, 1);
    
    cout << std::max(dp[1][0], dp[1][1]) << '\n';
    
    return 0;
}

洛谷-P3478 消防局的 STA-Station

题目大意

P3478 [POI 2008] STA-Station 题目大意

给定一个 n\large n 个点的树，请求出一个结点，使得以这个结点为根时，所有结点的深度之和最大。
一个结点的深度之定义为该节点到根的简单路径上边的数量。
数据范围：n≤106\large n \le 10^6.

思路

换根 DP。设 fu\large f_u 表示以 u\large u 为根节点的时候所有节点的深度之和是多少。换根一般都有两个 dfs\large dfs，我们在第一遍 dfs\large dfs 的时候记录节点的深度 dep\large dep，子树大小 size\large size，然后 fu\large f_u 的状态为：fu=depu\large f_u = dep_u。

在第二遍 dfsdfs 时，我们自上而下更新 fvf_v 的值，转移为：

fv=fu−sizev+n−sizev\large f_v = f_u - size_v + n - size_v

即子树 vv 内所有点的深度减一，子树外的所有深度加一。

注意 long long!!!

Code

Code

#include <bits/stdc++.h>

using std::cin;
using std::cout;

constexpr int N = 1e6 + 5;
int head[N], next[N << 1], to[N << 1], cnt = 0;
int n, u, v, dp[N], dep[N], size[N];

void AddEdge(const int u, const int v) {
    to[cnt] = v;
    next[cnt] = head[u];
    head[u] = cnt++;
}

void Dfs1(const int u, const int father) {
    dp[u] += dep[u];
    dep[u] = dep[father] + 1;
    size[N] = 1;
    
    for (register int i = head[u]; ~i; i = next[i]) {
        register const int v = to[i];
        if (v == father) continue;
        
        Dfs1(v, u);
        size[u] += size[v];
    }
}

void Dfs2(const int u, const int father) {
    for (register int i = head[u]; ~i; i = next[i]) {
        register const int v = to[i];
        if (v == father) continue;
        
        dp[v] = dp[u] - size[v] + n - size[v];
        Dfs2(v, u);
    }
}



int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
 
    std::memset(head, -1, sizeof(head));
    
    cin >> n;
    
    for (int i = 1; i < n; i++) {
        cin >> u >> v;
        
        AddEdge(u, v);
        AddEdge(v, u);
    }
    
    Dfs1(1, 1);
    Dfs2(1, 1);
    
    int ans = 1;
    for (int i = 2; i <= n; i++) {
        if (dp[i] > dp[ans]) ans = i;
    }
    
    cout << ans << '\n';
    
    return 0;
}