最大子树和

GitHub跳转原题关系图返回列表

用树形 DP 计算必须保留每个点时的最大连通块权值，负贡献子树直接剪掉。

OJ: luogu

题目 ID: P1122

难度:普及/提高-

标签:树形DP动态规划树

日期: 2026-06-22 23:07

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

给定一棵树，每个点有一个美丽指数，可以通过剪枝保留一个非空连通块。

要求保留下来的连通块点权和最大。

思路

先看一个可以直接验证想法的朴素解：

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

// brute.cpp：枚举小数据所有点集，检查是否连通。

const int MAXN = 22;

int n;
int beauty[MAXN];
bool edge_exists[MAXN][MAXN];

bool connected_subset(int mask) {
    int start = -1;
    for (int i = 0; i < n; i++) {
        if ((mask & (1 << i)) != 0) {
            start = i;
            break;
        }
    }
    if (start == -1) {
        return false;
    }

    queue<int> que;
    bool visited[MAXN] = {false};
    visited[start] = true;
    que.push(start);

    while (!que.empty()) {
        int u = que.front();
        que.pop();
        for (int v = 0; v < n; v++) {
            if ((mask & (1 << v)) != 0 && edge_exists[u + 1][v + 1] && !visited[v]) {
                visited[v] = true;
                que.push(v);
            }
        }
    }

    for (int i = 0; i < n; i++) {
        if ((mask & (1 << i)) != 0 && !visited[i]) {
            return false;
        }
    }
    return true;
}

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> beauty[i];
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        edge_exists[u][v] = true;
        edge_exists[v][u] = true;
    }

    int answer = -1000000000;
    for (int mask = 1; mask < (1 << n); mask++) {
        if (!connected_subset(mask)) {
            continue;
        }
        int sum = 0;
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) != 0) {
                sum += beauty[i + 1];
            }
        }
        answer = max(answer, sum);
    }
    cout << answer << '\n';

    return 0;
}

暴力枚举所有连通点集不可行。考虑树形 DP。

任选一个根。定义：

text
dp[u] = 必须保留 u，并且只在 u 的子树内选择连通块时的最大点权和

如果孩子 v 的 dp[v] 是正数，把它接到 u 上会让答案变大；如果是负数，就剪掉这个子树更好。

所以转移是：

text
dp[u] = beauty[u] + sum(max(0, dp[v]))

最终答案是所有 dp[u] 中的最大值。

代码

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

const int MAXN = 16005;

int n;
int beauty[MAXN];
vector<int> graph_edges[MAXN];
int dp[MAXN]; // dp[u] 表示必须保留 u，且只在 u 子树中选择连通块时的最大美丽和。
int answer;

void read_input() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> beauty[i];
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        graph_edges[u].push_back(v);
        graph_edges[v].push_back(u);
    }
}

void dfs(int u, int parent) {
    dp[u] = beauty[u];

    for (int i = 0; i < (int)graph_edges[u].size(); i++) {
        int v = graph_edges[u][i];
        if (v == parent) {
            continue;
        }
        dfs(v, u);

        // 子树贡献为正时才接到 u 上；负贡献剪掉更优。
        if (dp[v] > 0) {
            dp[u] += dp[v];
        }
    }

    answer = max(answer, dp[u]);
}

void solve() {
    answer = beauty[1];
    dfs(1, 0);
    cout << answer << '\n';
}

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

    read_input();
    solve();

    return 0;
}

复杂度

时间复杂度为 O(n)O(n)，空间复杂度为 O(n)O(n)。

总结

这道题的核心就是“负贡献剪掉”。

树上每个孩子方向互不影响，只要保留正贡献的子树，就能得到包含当前点的最优连通块。