设 dp[u] 表示必须包含 u 的最优连通块和，自底向上只吸收正贡献子树，就能在线性时间求树上最大连通子图和。
OJ: luogu
题目 ID: P8625
难度:普及/提高-
标签:树形DP树动态规划建模
日期: 2026-06-21 03:24
题意
给一棵带点权的树，可以选一个连通点集，要求点权和最大。
空集也允许，所以答案至少是 0。
思路
先看一个可以直接验证想法的朴素解：
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 25;
int n;
long long val[MAXN];
int adj[MAXN][MAXN];
bool is_connected_mask(int mask) {
if (mask == 0) {
return true;
}
int start = -1;
for (int i = 0; i < n; i++) {
if (mask & (1 << i)) {
start = i;
break;
}
}
queue<int> q;
int vis = 0;
q.push(start);
vis |= (1 << start);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v = 0; v < n; v++) {
if (!adj[u][v]) {
continue;
}
if (!(mask & (1 << v))) {
continue;
}
if (vis & (1 << v)) {
continue;
}
vis |= (1 << v);
q.push(v);
}
}
return vis == mask;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// 这是一个小数据精确暴力：
// 枚举点集，再判断是否连通并统计点权和。
cin >> n;
for (int i = 0; i < n; i++) {
cin >> val[i];
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
adj[i][j] = 0;
}
}
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
u--;
v--;
adj[u][v] = adj[v][u] = 1;
}
long long ans = 0;
int total = 1 << n;
for (int mask = 0; mask < total; mask++) {
if (!is_connected_mask(mask)) {
continue;
}
long long sum = 0;
for (int i = 0; i < n; i++) {
if (mask & (1 << i)) {
sum += val[i];
}
}
ans = max(ans, sum);
}
cout << ans << '\n';
return 0;
}brute.cpp 枚举所有点集，检查是否连通，再统计点权和。
这个做法完全正确，但只能处理很小的数据。
这题的关键是树形 DP。
设 dp[u] 表示：
- 选出的连通块必须包含
u - 并且这块连通结构只能通过
u再往父亲方向继续连
那么 u 的某个儿子子树要不要接上来，只看它的最优贡献 dp[v]：
- 若
dp[v] > 0，接上来会更优 - 若
dp[v] <= 0，不如不接
所以转移非常自然：
dp[u] = val[u] + sum(max(0, dp[v]))
其中 v 是 u 的所有儿子。
最后答案为什么是所有 dp[u] 的最大值？
因为任意一个非空最优连通块，都可以找到一个最靠近根的点。
把它看成这块连通结构的“顶端”，这整个连通块就一定被某个 dp[u] 覆盖。
再结合题目允许空集，所以最终答案应为：
max(0, 所有 dp[u] 的最大值)
这题样例可以用一棵小树来理解：
graph G {
1 [label="1"];
2 [label="-2"];
3 [label="-3"];
4 [label="4"];
5 [label="5"];
4 -- 2;
3 -- 1;
1 -- 2;
2 -- 5;
}
从这棵树中，最优连通块会选 4-2-5-1 这一部分，总和是：
4 + (-2) + 5 + 1 = 8
而点 3 的贡献是负数，所以不接进来更优。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000 + 5;
int n;
long long val[MAXN];
vector<int> g[MAXN];
int parent_arr[MAXN];
long long dp[MAXN];
long long ans;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> val[i];
g[i].clear();
}
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
vector<int> order;
order.reserve(n);
stack<int> st;
st.push(1);
parent_arr[1] = 0;
while (!st.empty()) {
int u = st.top();
st.pop();
order.push_back(u);
for (size_t i = 0; i < g[u].size(); i++) {
int v = g[u][i];
if (v == parent_arr[u]) {
continue;
}
parent_arr[v] = u;
st.push(v);
}
}
ans = -(1LL << 60);
for (int idx = (int)order.size() - 1; idx >= 0; idx--) {
int u = order[idx];
dp[u] = val[u];
// 只有对子树贡献为正时，才值得把这棵子树连进来。
for (size_t i = 0; i < g[u].size(); i++) {
int v = g[u][i];
if (v == parent_arr[u]) {
continue;
}
if (dp[v] > 0) {
dp[u] += dp[v];
}
}
ans = max(ans, dp[u]);
}
if (ans < 0) {
ans = 0;
}
cout << ans << '\n';
return 0;
}复杂度
整棵树只需要一次遍历和一次倒序 DP。
时间复杂度是
总结
这题最核心的判断只有一句话：
- 一棵子树如果能提供正贡献，就接；否则就不要
这是树上“最大连通子图和”最典型的树形 DP 思路。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
