蓝桥杯经典真题解析：生命之树问题的树形DP解法（含完整代码实现）

10小时前比赛题解29

一、问题背景与题意分析

题目来源：2015年蓝桥杯省赛B组真题（洛谷P8625）
问题描述：给定一棵n个节点的树，每个节点有整数权值。需要找到一个连通子树，使其节点权值之和最大。

关键点说明：

子树必须连通（任意两节点间有唯一路径）
权值可能为负数
数据规模：1≤n≤1e5

二、算法核心思想

采用树形动态规划（Tree DP）的解法，通过后序遍历计算每个子树的最大和。

状态定义：

f[u]表示以节点u为根的子树能获得的最大权值和

转移方程：

f[u] = w[u] + \sum_{v \in children(u)} max(0, f[v])

贪心策略：只累加正数子树的贡献

三、代码逐行详解

#include <iostream>
#include <vector>
#include <algorithm>
using namespACe std;

const int MAXN = 1e5 + 10;  // 最大节点数+10的缓冲
vector<int> g[MAXN];  // 邻接表存储树结构
int w[MAXN];         // 节点权值数组
long long f[MAXN];   // DP状态数组
long long res = -1e18; // 存储最终结果，初始化为极小值

// 深度优先搜索函数
// u: 当前节点  fa: 父节点（防止回退）
void dfs(int u, int fa) {
    f[u] = w[u];  // 初始化为自身权值
    for (int v : g[u]) {  // 遍历所有邻接节点
        if (v == fa) continue;  // 跳过父节点防环
        dfs(v, u);  // 递归处理子节点
        if (f[v] > 0) f[u] += f[v]; // 贪心：只加正贡献
    }
    res = max(res, f[u]);  // 更新全局最大值
}

int main() {
    ios::sync_with_stdio(false);  // 关闭同步提升IO速度
    cin.tie(nullptr);            // 解除cin与cout的绑定
    
    int n;
    cin >> n;
    // 读取节点权值
    for (int i = 1; i <= n; ++i) cin >> w[i]; 
    // 构建树结构
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);  // 无向图双向添加
        g[v].push_back(u);
    }
    
    dfs(1, -1);  // 从根节点1开始DFS，初始父节点为-1
    cout << res << endl;
    return 0;
}