2025 Summer Day8

Content：DP (Interval, Tree)

Date：2025.7.24

概览

区间 DP
树形 DP

例题

洛谷-P4516 潜入行动

题目大意

题目大意

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

思路

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

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

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

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

\large f_{u,i,0,0} = \sum_{v \in \operatorname{son}(u)} f_{u,i - j,0,0} \times f_{v,j,0,1}

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

\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}

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

\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})

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

\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

1
#include <bits/stdc++.h>
2

3
namespace IO {
4
    template<typename name> name read() {
5
        name x = 0, f = 1; char ch = getchar();
6
        while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
7
        while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
8
        return x * f;
9
    }
10
    template<typename name> void _write(name x) {
11
        if (x > 9) _write(x / 10);
12
        putchar(x % 10 + '0');
13
    }
14
    template<typename name> void write(name x) {
15
        if (x < 0) putchar('-'), x = -x;
16
        _write(x);
17
    }
18
}
19

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

25
inline void AddEdge(const int u, const int v) {
26
    to[cnt] = v;
27
    next[cnt] = head[u];
28
    head[u] = cnt++;
29
}
30

31
inline void Dfs(int u, int father) {
32
    dp[u][0][0][0] = dp[u][1][1][0] = 1;
33
    size[u] = 1;
34

35
    for (int i = head[u]; ~i; i = next[i]) {
36
        const int v = to[i];
37
        if (v == father) continue;
38

39
        Dfs(v, u);
40
        size[u] += size[v];
41

42
        // ! 这里要进行备份，不然转移的时候会出现问题（用已修改的状态修改未修改的状态）
43
        for (int t = 0; t <= std::min(k, size[u]); t++) {
44
            tmp[t][0][0] = dp[u][t][0][0];
45
            tmp[t][1][0] = dp[u][t][1][0];
46
            tmp[t][0][1] = dp[u][t][0][1];
47
            tmp[t][1][1] = dp[u][t][1][1];
48
            dp[u][t][0][0] = dp[u][t][1][0] = dp[u][t][0][1] = dp[u][t][1][1] = 0;
49
        }
50

51
        // ! 注意枚举范围，不能直接枚举区间 [0,k]，不然会 TLE
52
        for (int t = 0; t <= std::min(size[u], k); t++) {
53
            // ! 这里同理
54
            for (int j = 0; j <= std::min(size[v], t); j++) {
55
                if (t - j > size[u] - size[v]) continue;
56

57
                // // 可恶的转移
58
                (dp[u][t][0][0] += (long long) tmp[t - j][0][0] * dp[v][j][0][1] % MOD) %= MOD;
59
                (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;
60
                (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;
61
                (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;
62
            }
63
        }
64
    }
65
}
66

67
int main() {
68
    using namespace IO;
69

70
    n = read<int>();
71
    k = read<int>();
72

73
    for (int i = 1; i <= n; i++) head[i] = -1;
74

75
    for (int i = 1; i < n; i++) {
76
        u = read<int>(), v = read<int>();
77
        AddEdge(u, v);
78
        AddEdge(v, u);
79
    }
80

81
    Dfs(1, 1);
82

83
    write((1ll * dp[1][k][0][1] + dp[1][k][1][1]) % MOD);
84

85
    return 0;
86
}

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

题目大意

题目大意

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

思路

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

转移如下：

\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}

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

Code

Code

1
#include <bits/stdc++.h>
2

3
using std::cin;
4
using std::cout;
5

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

11
void add_edge(const int u, const int v) {
12
    to[cnt] = v;
13
    next[cnt] = head[u];
14
    head[u] = cnt++;
15
}
16

17
void dfs(const int u, const int father) {
18
    dp[u][1] = r[u];
19

20
    for (int i = head[u]; ~i; i = next[i]) {
21
        const int v = to[i];
22
        if (v == father) continue;
23

24
        dfs(v, u);
25
        dp[u][0] += std::max(dp[v][0], dp[v][1]);
26
        dp[u][1] += dp[v][0];
27
    }
28
}
29

30
int main() {
31
    std::ios::sync_with_stdio(false);
32
    cin.tie(nullptr);
33
    cout.tie(nullptr);
34

35
    std::memset(head, -1, sizeof(head));
36

37
    cin >> n;
38

39
    for (int i = 1; i <= n; i++) {
40
        cin >> r[i];
41
    }
42

43
    for (int i = 1; i < n; i++) {
44
        cin >> u >> v;
45
        add_edge(u, v);
46
        add_edge(v, u);
47
    }
48

49
    dfs(1, 1);
50

51
    cout << std::max(dp[1][0], dp[1][1]) << '\n';
52

53
    return 0;
54
}

洛谷-P3478 消防局的 STA-Station

题目大意

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

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

思路

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

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

\large f_v = f_u - size_v + n - size_v

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

注意 long long!!!

Code

Code

1
#include <bits/stdc++.h>
2

3
using std::cin;
4
using std::cout;
5

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

10
void AddEdge(const int u, const int v) {
11
    to[cnt] = v;
12
    next[cnt] = head[u];
13
    head[u] = cnt++;
14
}
15

16
void Dfs1(const int u, const int father) {
17
    dp[u] += dep[u];
18
    dep[u] = dep[father] + 1;
19
    size[N] = 1;
20

21
    for (register int i = head[u]; ~i; i = next[i]) {
22
        register const int v = to[i];
23
        if (v == father) continue;
24

25
        Dfs1(v, u);
26
        size[u] += size[v];
27
    }
28
}
29

30
void Dfs2(const int u, const int father) {
31
    for (register int i = head[u]; ~i; i = next[i]) {
32
        register const int v = to[i];
33
        if (v == father) continue;
34

35
        dp[v] = dp[u] - size[v] + n - size[v];
36
        Dfs2(v, u);
37
    }
38
}
39

40

41

42
int main() {
43
    std::ios::sync_with_stdio(false);
44
    cin.tie(nullptr);
45
    cout.tie(nullptr);
46

47
    std::memset(head, -1, sizeof(head));
48

49
    cin >> n;
50

51
    for (int i = 1; i < n; i++) {
52
        cin >> u >> v;
53

54
        AddEdge(u, v);
55
        AddEdge(v, u);
56
    }
57

58
    Dfs1(1, 1);
59
    Dfs2(1, 1);
60

61
    int ans = 1;
62
    for (int i = 2; i <= n; i++) {
63
        if (dp[i] > dp[ans]) ans = i;
64
    }
65

66
    cout << ans << '\n';
67

68
    return 0;
69
}