What is the main idea in Maximum Score After Applying Operations on a Tree?

Compute the minimum value that must stay in the tree to keep every root-to-leaf path nonzero, then subtract that from the total sum. This turns the problem into a DFS plus subtree DP.

Why is the leaf case so important in this problem?

A leaf path contains no deeper node to rescue it. If a leaf subtree kept value becomes 0, that entire root-to-leaf path can become zero, so dp at a leaf must equal the leaf's own value.

Why does the transition use min(subtreeSum, sum of child dp values)?

Keeping subtreeSum means preserving everything under that node. Keeping sum of child dp values means removing the current node's value and relying on each child subtree to preserve just enough value, so you take the cheaper valid option.

Is this really a binary-tree traversal and state tracking problem?

The pattern is broader than binary trees because the input tree can have any number of children. The useful part of the hint is state tracking during postorder traversal: each node combines child states and subtree sums.

Can this be solved greedily or with a simple path check?

No, because a choice at one node changes what every descendant path is allowed to lose. The dependency is subtree-wide, which is why the DP state per node is needed instead of local greedy decisions.

#2925

Medium

auto_awesome二分·树·traversal

LeetCode 题解工作台

在树上执行操作以后得到的最大分数

有一棵 n 个节点的无向树，节点编号为 0 到 n - 1 ，根节点编号为 0 。给你一个长度为 n - 1 的二维整数数组 edges 表示这棵树，其中 edges[i] = [a i , b i ] 表示树中节点 a i 和 b i 有一条边。同时给你一个长度为 n 下标从 0 开始的整数数组…

动态规划树深度优先搜索

题目描述

有一棵 n 个节点的无向树，节点编号为 0 到 n - 1 ，根节点编号为 0 。给你一个长度为 n - 1 的二维整数数组 edges 表示这棵树，其中 edges[i] = [a_i, b_i] 表示树中节点 a_i 和 b_i 有一条边。

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

一开始你的分数为 0 ，每次操作中，你将执行：

选择节点 i 。
将 values[i] 加入你的分数。
将 values[i] 变为 0 。

如果从根节点出发，到任意叶子节点经过的路径上的节点值之和都不等于 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 。根节点的值是非 0 的。所以从根出发到任意叶子节点路径上节点值之和都不为 0 。所以树是健康的。你的得分之和为 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⁴
edges.length == n - 1
edges[i].length == 2
0 <= a_i, b_i < n
values.length == n
1 <= values[i] <= 10⁹
输入保证 edges 构成一棵合法的树。

lightbulb

解题思路

方法一：树形 DP

题目实际上是让我们从树的所有节点中选出一些节点，使得这些节点的值之和最大，并且每条从根节点到叶子节点的路径上都有一个点没有被选中。

我们可以使用树形 DP 的方法解决这个问题。

我们设计一个函数 $dfs(i, fa)$ ，其中 $i$ 表示当前以节点 $i$ 作为子树的根节点，且 $fa$ 表示 $i$ 的父节点，函数返回一个长度为 $2$ 的数组，其中 $[0]$ 表示该子树中所有节点的值之和，而 $[1]$ 表示该子树满足每条路径上都有一个点没有被选中的最大值。

其中 $[0]$ 的值可以直接通过 DFS 累加每个节点的值得到，而 $[1]$ 的值，则需要考虑两种情况，即节点 $i$ 是否被选中。如果被选中，那么节点 $i$ 的每个子树得必须满足每条路径上都有一个点没有被选中；如果没有被选中，那么节点 $i$ 的每个子树可以选取所有节点。我们取这两种情况中的最大值即可。

需要注意的是，叶子节点的 $[1]$ 的值为 $0$ ，因为叶子节点没有子树，所以不需要考虑每条路径上都有一个点没有被选中的情况。

答案为 $dfs(0, -1)[1]$ 。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为节点数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

class Solution:
    def maximumScoreAfterOperations(
        self, edges: List[List[int]], values: List[int]
    ) -> int:
        def dfs(i: int, fa: int = -1) -> (int, int):
            a = b = 0
            leaf = True
            for j in g[i]:
                if j != fa:
                    leaf = False
                    aa, bb = dfs(j, i)
                    a += aa
                    b += bb
            if leaf:
                return values[i], 0
            return values[i] + a, max(values[i] + b, a)

        g = [[] for _ in range(len(values))]
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)
        return dfs(0)[1]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
They want you to convert a global healthy-path rule into a local subtree DP state.
question_mark
They expect you to notice that maximizing score is equivalent to minimizing the value that must remain.
question_mark
They are testing whether you can write a parent-aware DFS on an undirected tree without revisiting nodes.

warning

常见陷阱

外企场景

error
Treating this as a greedy pick-the-largest-values problem and breaking a leaf path by removing its only remaining value.
error
Using the wrong base case for leaves; dp[leaf] is values[leaf], not 0.
error
Forgetting that the graph is undirected and recursing back to the parent, which corrupts subtree sums and causes cycles.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return the minimum value that must remain instead of the maximum score; that is exactly dp[0].
arrow_right_alt
Change the healthy rule so every root-to-leaf path must stay at least K, which would alter the subtree state and transition.
arrow_right_alt
Ask for an iterative postorder traversal version to avoid recursion depth concerns on a long chain tree.

help

常见问题

外企场景

继续练习

#2920 收集所有金币可获得的最大积分 #2973 树中每个节点放置的金币数目 #2867 统计树中的合法路径数目