Medium

题目描述

有一棵包含 n 个节点的无向树，节点编号从 0 到 n - 1，以节点 0 为根。给你一个长度为 n - 1 的二维整数数组 edges，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间有一条边。

同时给你一个长度为 n 的下标从 0 开始的整数数组 values，其中 values[i] 是与第 i 个节点相关联的值。

你从得分 0 开始。在一次操作中，你可以：

  • 选择任意节点 i
  • 将 values[i] 加到你的得分中
  • 将 values[i] 设为 0

如果从根到任意叶节点的路径上的值的总和都不等于零，则树是健康的。

返回在保持树健康的前提下，经过任意次数的操作后你能获得的最大得分。

示例 1：

输入：edges = [[0,1],[0,2],[0,3],[2,4],[4,5]], values = [5,2,5,2,1,1]
输出：11
解释：我们可以选择节点 1, 2, 3, 4, 5。根的值非零。因此，从根到任意叶的路径上值的总和都不等于零。因此，树是健康的，得分是 values[1] + values[2] + values[3] + values[4] + values[5] = 11。
可以证明 11 是在树上进行任意次数操作后可获得的最大得分。

示例 2：

输入：edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]], values = [20,10,9,7,4,3,5]
输出：40
解释：我们可以选择节点 0, 2, 3, 4。
- 从 0 到 4 的路径上值的总和等于 10。
- 从 0 到 3 的路径上值的总和等于 10。
- 从 0 到 5 的路径上值的总和等于 3。
- 从 0 到 6 的路径上值的总和等于 5。
因此，树是健康的，得分是 values[0] + values[2] + values[3] + values[4] = 40。
可以证明 40 是在树上进行任意次数操作后可获得的最大得分。

约束条件：

  • 2 <= n <= 2 * 10^4
  • edges.length == n - 1
  • edges[i].length == 2
  • 0 <= ai, bi < n
  • values.length == n
  • 1 <= values[i] <= 10^9
  • 输入保证 edges 表示一个有效的树

解题思路

这是一道树形动态规划问题。关键在于理解"健康树"的定义：从根到任意叶节点的路径上值的总和都不为零。

核心思路： 对于每个节点，我们有两种选择：

  1. 选择当前节点的值：将其加入得分，此时子树中的节点可以自由选择（因为从根到叶的路径已经保证有当前节点的值）
  2. 不选择当前节点的值：为了保证路径和不为零，每个子树中必须至少保留一些值来维持健康性

状态定义：

  • dp[i]：以节点 i 为根的子树能获得的最大得分
  • sum[i]：以节点 i 为根的子树所有节点值的总和

状态转移： 对于节点 x：

  • 如果选择 values[x]：得分 = values[x] + Σ dp[child]（所有子树都可以自由选择）
  • 如果不选择 values[x]：得分 = Σ sum[child]（每个子树必须保留所有值来维持健康）

取两种选择的最大值：dp[x] = max(values[x] + Σ dp[child], Σ sum[child])

特殊情况：

  • 叶节点必须保留其值（否则路径和为0）
  • 根节点可以自由选择

代码实现

class Solution {
public:
    long long maximumScoreAfterOperations(vector<vector<int>>& edges, vector<int>& values) {
        int n = values.size();
        vector<vector<int>> graph(n);
        
        for (auto& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }
        
        function<pair<long long, long long>(int, int)> dfs = [&](int node, int parent) -> pair<long long, long long> {
            long long sum = values[node];
            long long dp = 0;
            
            for (int child : graph[node]) {
                if (child != parent) {
                    auto [childDp, childSum] = dfs(child, node);
                    sum += childSum;
                    dp += childDp;
                }
            }
            
            // 如果是叶节点，必须保留当前值
            if (graph[node].size() == 1 && node != 0) {
                return {sum, sum};
            }
            
            // 选择当前节点值 vs 不选择（保持子树完整）
            long long takeNode = values[node] + dp;
            long long keepSubtrees = sum - values[node];
            
            return {max(takeNode, keepSubtrees), sum};
        };
        
        return dfs(0, -1).first;
    }
};

class Solution:
    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:
        n = len(values)
        graph = [[] for _ in range(n)]
        
        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)
        
        def dfs(node, parent):
            total_sum = values[node]
            dp_sum = 0
            
            for child in graph[node]:
                if child != parent:
                    child_dp, child_sum = dfs(child, node)
                    total_sum += child_sum
                    dp_sum += child_dp
            
            # 如果是叶节点，必须保留当前值
            if len(graph[node]) == 1 and node != 0:
                return total_sum, total_sum
            
            # 选择当前节点值 vs 不选择（保持子树完整）
            take_node = values[node] + dp_sum
            keep_subtrees = total_sum - values[node]
            
            return max(take_node, keep_subtrees), total_sum
        
        return dfs(0, -1)[0]

public class Solution {
    public long MaximumScoreAfterOperations(int[][] edges, int[] values) {
        int n = values.Length;
        List<int>[] graph = new List<int>[n];
        
        for (int i = 0; i < n; i++) {
            graph[i] = new List<int>();
        }
        
        foreach (var edge in edges) {
            graph[edge[0]].Add(edge[1]);
            graph[edge[1]].Add(edge[0]);
        }
        
        (long dp, long sum) Dfs(int node, int parent) {
            long totalSum = values[node];
            long dpSum = 0;
            
            foreach (int child in graph[node]) {
                if (child != parent) {
                    var (childDp, childSum) = Dfs(child, node);
                    totalSum += childSum;
                    dpSum += childDp;
                }
            }
            
            // 如果是叶节点，必须保留当前值
            if (graph[node].Count == 1 && node != 0) {
                return (totalSum, totalSum);
            }
            
            // 选择当前节点值 vs 不选择（保持子树完整）
            long takeNode = values[node] + dpSum;
            long keepSubtrees = totalSum - values[node];
            
            return (Math.Max(takeNode, keepSubtrees), totalSum);
        }
        
        return Dfs(0, -1).dp;
    }
}

var maximumScoreAfterOperations = function(edges, values) {
    const n = values.length;
    const graph = Array(n).fill().map(() => []);
    
    for (const [a, b] of edges) {
        graph[a].push(b);
        graph[b].push(a);
    }
    
    function dfs(node, parent) {
        let subtreeSum = values[node];
        let maxScore = 0;
        
        for (const child of graph[node]) {
            if (child !== parent) {
                const [childSubtreeSum, childMaxScore] = dfs(child, node);
                subtreeSum += childSubtreeSum;
                maxScore += childMaxScore;
            }
        }
        
        if (graph[node].length === 1 && node !== 0) {
            return [subtreeSum, 0];
        }
        
        return [subtreeSum, Math.max(maxScore, subtreeSum - values[node])];
    }
    
    return dfs(0, -1)[1];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(n)

说明：

  • 时间复杂度：每个节点访问一次，每条边遍历两次，总体为 O(n)
  • 空间复杂度：递归栈深度最坏情况为 O(n)，图的邻接表存储需要 O(n) 空间

相关题目