跳转至

树形dp

习题

P2458 [SDOI2006] 保安站岗 - 洛谷

每个点都必须被看守，花费 \(v_i\) 在点 \(i\) 放置一个保安，保安可以看守这个点及这个点所有相邻的点

问使所有点被看守的花费的最小值

代码
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
vector<int> adj[1505];
int dp[1505][3];
// 0 表示自身节点
// 1 表示子节点
// 2 表示父节点
void dfs(int u, int p) {
    int res = 0x7fffffff;
    for (auto &to : adj[u]) {
        if (to == p) continue;
        dfs(to, u);
        // 如果子节点有, 那么一定要保证一个子节点有.
        // 如果子节点有的本来就小, 那么无需选择. 否则我们选择减去孙子节点，加上子节点.
        res = min(res, dp[to][0] - min(dp[to][0], dp[to][1]));
        // 如果自身节点有, 那么可任意选
        dp[u][0] += min({dp[to][0], dp[to][1], dp[to][2]});
        // 如果子节点有, 那么先选子节点和孙子节点的最小
        dp[u][1] += min(dp[to][0], dp[to][1]);
        // 如果父节点有, 那么可选子节点或孙子节点的最小
        dp[u][2] += min(dp[to][0], dp[to][1]);
    }
    dp[u][1] += res;
}
int main() {
    int n;
    cin >> n;
    for (int i = 0 ; i < n ; i++) {
        int p, m;
        cin >> p >> dp[p][0] >> m;
        for (int j = 0 ; j < m ; j++) {
            int x;
            cin >> x;
            adj[p].emplace_back(x);
            adj[x].emplace_back(p);
        }
    }
    dfs(1, 0);
    cout << min(dp[1][0], dp[1][1]);
    return 0;
}

P1352 没有上司的舞会 - 洛谷

\(n\) 个节点的树，每个点有价值 \(v_i\)，选择点 \(i\) 则不能选择该点的儿子。

问价值和的最大。

代码
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
vector<int> a;
vector<vector<int>> dp, adj;
void dfs(int u) {
    dp[u][0] = 0;
    dp[u][1] = a[u];
    for (auto &i : adj[u]) {
        dfs(i);
        dp[u][0] += max(dp[i][0], dp[i][1]);
        dp[u][1] += dp[i][0];
    }
}
int main() {
    int n;
    cin >> n;
    a.resize(n + 1);
    adj.resize(n + 1);
    dp.resize(n + 1, vector<int>(2));
    for (int i = 1 ; i <= n ; i++) cin >> a[i];
    vector vis(n + 1, 0);
    for (int i = 1 ; i < n ; i++) {
        int x, y;
        cin >> x >> y;
        adj[y].emplace_back(x);
        vis[x] = 1;
    }
    int root = 1;
    for (int i = 1 ; i <= n ; i++) {
        if (vis[i] == 0) {
            root = i;
            break;
        }
    }
    dfs(root);
    cout << max(dp[root][0], dp[root][1]);
    return 0;
}

F-树上子链_牛客竞赛动态规划专题班树型dp例题

一棵树, 点权有正有负, 问子链权值和的最大

代码
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;
// 2024 OneWan
vector<int> adj[100005];
long long dp[100005];
long long a[100005];
long long ans = -1e18;
void dfs(int u, int p) {
    dp[u] = a[u];
    for (auto &to : adj[u]) {
        if (to == p) continue;
        dfs(to, u);
        ans = max(ans, dp[u] + dp[to]);
        dp[u] = max(dp[u], a[u] + dp[to]);
    }
    ans = max(ans, dp[u]);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
    }
    for (int i = 1 ; i < n ; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, 0);
    cout << ans;
    return 0;
}

P2014 [CTSC1997] 选课 - 洛谷

代码
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
vector<int> adj[305];
int val[305];
int dp[305][305];
int n, m;
int dfs(int u) {
    int p = 1;
    dp[u][1] = val[u];
    for (auto &v : adj[u]) {
        int cnt = dfs(v);
        for (int i = min(p, m + 1) ; i > 0 ; i--) {
            for (int j = 1 ; j <= cnt && i + j <= m + 1 ; j++) {
                dp[u][i + j] = max(dp[u][i + j], dp[u][i] + dp[v][j]);
            }
        }
        p += cnt;
    }
    return p;
}
int main() {
    cin >> n >> m;
    for (int i = 1 ; i <= n ; i++) {
        int s;
        cin >> s >> val[i];
        adj[s].emplace_back(i);
    }
    dfs(0);
    cout << dp[0][m + 1];
    return 0;
}