maximum-score-after-applying-operations-on-a-tree

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Let <code>dp[i]</code> be the maximum score we can get on the subtree rooted at <code>i</code> and <code>sum[i]</code> be the sum of all the values of the subtree rooted at <code>i</code>.

If we don’t take <code>value[i]</code> into the final score, we can take all the nodes of the subtrees rooted at <code>i</code>’s children.

If we take <code>value[i]</code> into the score, then each subtree rooted at its children should satisfy the constraints.

<code>dp[x] = max(value[x] + sigma(dp[y]), sigma(sum[y]))</code>, where <code>y</code> is a direct child of <code>x</code>.

Algorithms

There is an undirected tree with <code>n</code> nodes labeled from 0 to <code>n - 1</code>, and rooted at node 0. You are given&nbsp;a 2D integer array <code>edges</code> of length <code>n - 1</code>, where <code>edges[i] = [ai, bi]</code> indicates that there is an edge between nodes <code>ai</code> and <code>bi</code> in the tree.

You are also given a 0-indexed integer array <code>values</code> of length <code>n</code>, where <code>values[i]</code> is the value associated with the <code>ith</code> node.

You start with a score of 0. In one operation, you choose a node <code>i</code>, add <code>values[i]</code> to your score, and then set <code>values[i]</code> to 0. All three steps happen together as a single operation.

A tree is healthy if, for every leaf node, the sum of the current values on the path from the root to that leaf is not equal to 0.

Return the maximum score you can obtain by performing this operation on the tree any number of times, so that the tree remains healthy at the end.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2023/10/11/graph-13-1.png" style="width: 515px; height: 443px;" />
<pre>
Input: edges = [[0,1],[0,2],[0,3],[2,4],[4,5]], values = [5,2,5,2,1,1]
Output: 11
Explanation: We apply the operation to nodes 1, 2, 3, 4, and 5, so the values become [5,0,0,0,0,0]. The leaves are nodes 1, 3, and 5.
- The sum of values on the path from 0 to 1 is equal to 5.
- The sum of values on the path from 0 to 3 is equal to 5.
- The sum of values on the path from 0 to 5 is equal to 5.
Every leaf has a non-zero path sum, so the tree is healthy. The score is the sum of the original values of the chosen nodes: 2 + 5 + 2 + 1 + 1 = 11.
It can be shown that 11 is the maximum score obtainable by performing any number of operations on the tree.
</pre>

Example 2:
<img alt="" src="https://assets.leetcode.com/uploads/2023/10/11/graph-14-2.png" style="width: 522px; height: 245px;" />
<pre>
Input: edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]], values = [20,10,9,7,4,3,5]
Output: 40
Explanation: We apply the operation to nodes 0, 2, 3, and 4, so the values become [0,10,0,0,0,3,5]. The leaves are nodes 3, 4, 5, and 6.
- The sum of values on the path from 0 to 3 is equal to 10.
- The sum of values on the path from 0 to 4 is equal to 10.
- The sum of values on the path from 0 to 5 is equal to 3.
- The sum of values on the path from 0 to 6 is equal to 5.
Every leaf has a non-zero path sum, so the tree is healthy. The score is the sum of the original values of the chosen nodes: 20 + 9 + 7 + 4 = 40.
It can be shown that 40 is the maximum score obtainable by performing any number of operations on the tree.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>2 &lt;= n &lt;= 2 * 104</code></li>
	<li><code>edges.length == n - 1</code></li>
	<li><code>edges[i].length == 2</code></li>
	<li><code>0 &lt;= ai, bi &lt; n</code></li>
	<li><code>values.length == n</code></li>
	<li><code>1 &lt;= values[i] &lt;= 109</code></li>
	<li>The input is generated such that <code>edges</code> represents a valid tree.</li>
</ul>

第 370 场周赛

weekly-contest-370

maximumScoreAfterOperations

资深工程师

Maximum Score After Applying Operations on a Tree

Sum of Distances in Tree

sum-of-distances-in-tree

树中距离之和

Collect Coins in a Tree

collect-coins-in-a-tree

收集树中金币

Find the Maximum Sum of Node Values

find-the-maximum-sum-of-node-values

最大节点价值之和

Tree

Depth-First Search

Dynamic Programming

树形 DP

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

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

一开始你的分数为 0。在一次操作中，你选择一个节点 <code>i</code>，将 <code>values[i]</code> 的值 加 到你的得分上，然后将 <code>values[i]</code> 设置 为 0。这三个步骤作为一个单一操作同时发生。

如果从根节点出发，到 任意 叶子节点经过的路径上的节点值之和都 不等于 0 ，那么我们称这棵树是 健康的&nbsp;。

你可以对这棵树执行任意次操作，但要求执行完所有操作以后树是&nbsp;健康的&nbsp;，请你返回你可以获得的 最大分数&nbsp;。

&nbsp;

示例 1：

<img alt="" src="https://assets.leetcode.com/uploads/2023/10/11/graph-13-1.png" style="width: 515px; height: 443px;" />

<pre>
输入：edges = [[0,1],[0,2],[0,3],[2,4],[4,5]], values = [5,2,5,2,1,1]
输出：11
解释：我们对节点 1、2、3、4 和 5 进行操作，因此值变为 [5,0,0,0,0,0]。叶子节点是节点 1、3 和 5。
- 从 0 到 1 的路径上值的总和等于 5。
- 从 0 到 3 的路径上值的总和等于 5。
- 从 0 到 5 的路径上值的总和等于 5。
每个叶子节点都有非零的路径和，所以树是健康的。得分是所选节点的原始值的总和：2 + 5 + 2 + 1 + 1 = 11。
可以证明 11 是通过在树上执行任何数量的操作所能获得的最大分数。
</pre>

示例 2：

<img alt="" src="https://assets.leetcode.com/uploads/2023/10/11/graph-14-2.png" style="width: 522px; height: 245px;" />

<pre>
输入：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,10,0,0,0,3,5]。叶子节点是节点 3、4、5 和 6。
- 从 0 到 3 的路径上值的总和等于 10。
- 从 0 到 4 的路径上值的总和等于 10。
- 从 0 到 5 的路径上值的总和等于 3。
- 从 0 到 6 的路径上值的总和等于 5。
每个叶子节点都有非零的路径和，所以树是健康的。得分是所选节点原始值的总和：20 + 9 + 7 + 4 = 40。
可以证明 40 是通过在树上执行任何数量的操作所能获得的最高分数。</pre>

&nbsp;

提示：

<ul>
	<li><code>2 &lt;= n &lt;= 2 * 104</code></li>
	<li><code>edges.length == n - 1</code></li>
	<li><code>edges[i].length == 2</code></li>
	<li><code>0 &lt;= ai, bi &lt; n</code></li>
	<li><code>values.length == n</code></li>
	<li><code>1 &lt;= values[i] &lt;= 109</code></li>
	<li>输入保证&nbsp;<code>edges</code>&nbsp;构成一棵合法的树。</li>
</ul>