以练代学：用竞赛真题学算法——树形DP

先上题目出自蓝桥杯省赛真题题目描述X 森林里上帝创建了生命之树树上每个节点都有一个和谐值。现在需要选出一个连通的节点集合 S满足集合内任意两点都可以通过集合内的节点互相连通。在满足连通的前提下要求集合内所有节点和谐值之和最大求出这个最大总和。集合可以为空空集权值为 0。输入描述第一行一个整数 n表示树的节点总数。第二行 n 个整数表示 1~n 号节点各自的和谐值。接下来 n-1 行每行两个整数 u,v表示 u 和 v 之间有一条无向边。数据保证是一棵树无环、连通。数据范围0n≤105点权绝对值不超过106。输出描述输出一个整数表示最大评分最大连通子树权值和。问题分析本题要求选出树上连通的一块区域使得权值总和最大是蓝桥杯最标准的树上最大子段和问题。首先明确题目条件选出的集合必须连通不能零散选取多个不相连的点。想要总和最大贪心思路非常清晰对于任意一个节点如果它的子树能带来正向收益就选择合并进来如果子树收益为负数就舍弃不选。我们采用深度优先遍历整棵树从叶子节点向上递推计算答案。因为树是无向边存储遍历时需要记录父节点防止走回头路重复遍历。定义dp[u] 表示必须选上 u 节点时以 u 为根的子树能选出的最大连通权值和。状态转移逻辑初始时dp[u]等于节点 u 自身权值。遍历 u 的所有子节点 v如果子节点的最优值dp[v]0说明选上 v 能让总和变大就把dp[v]加到dp[u]中如果dp[v]≤0选上会拉低总和直接不选取该子树。在遍历整棵树的过程中记录所有节点dp[u]的最大值这个最大值就是树上最优连通块的答案。最后需要和 0 取最大值因为题目允许选空集当所有点权都是负数时最优解就是不选任何点答案为 0。整体遍历每个节点、每条边仅一次时间复杂度O(n)可以完美处理105规模的数据不会超时。代码演示C#include iostream #include vector #include algorithm using namespace std; typedef long long ll; const int N 100010; vectorint adj[N]; ll val[N], dp[N]; ll ans 0; void dfs(int u, int fa) { dp[u] val[u]; for (int v : adj[u]) { if (v fa) continue; dfs(v, u); if (dp[v] 0) dp[u] dp[v]; } ans max(ans, dp[u]); } int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin n; for (int i 1; i n; i) cin val[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, -1); cout ans endl; return 0; }pythonimport sys sys.setrecursionlimit(1 25) n int(sys.stdin.readline()) val list(map(int, sys.stdin.readline().split())) adj [[] for _ in range(n)] for _ in range(n-1): u, v map(int, sys.stdin.readline().split()) u - 1 v - 1 adj[u].append(v) adj[v].append(u) dp [0]*n ans 0 def dfs(u, fa): global ans dp[u] val[u] for v in adj[u]: if v fa: continue dfs(v, u) if dp[v] 0: dp[u] dp[v] ans max(ans, dp[u]) dfs(0, -1) print(ans)算法详解代码整体分为建图、深度优先遍历、答案更新三个部分逻辑简洁清晰。首先用邻接表存储树的无向边节点编号 1 开始C/0 开始Python方便处理。dfs 函数中当前节点 u 先初始化为自身权值再遍历所有相邻节点跳过父节点后递归处理子节点。子节点计算完成后判断子节点最优值是否为正数正数就合并负数直接舍弃。每计算完一个节点的 dp 值就全局更新最大值 ans。dp [u] 的含义严格保证连通性必须选 u才能合并子树天然满足题目连通要求不需要额外判断连通性。因为只遍历每个点每条边一次复杂度线性对于 1e5 数据完全稳定。需要注意节点权值可能为负数必须用 long long 存储答案防止溢出同时允许空集ans 初始化为 0不需要额外处理全负数情况。本题是蓝桥杯树上贪心递推的经典原题代码模板可以直接套用在所有树上最大连通子块、最大子树和同类题目中。结语生命之树是蓝桥杯树上递推计算的代表性题目思路简洁高效不需要复杂算法核心就是子树收益为正则选为负则弃。