Maximum Score After Applying Operations on a Tree — Solution
Maximum Score After Applying Operations on a Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Maximum Score After Applying Operations on a Tree is a medium coding problem on dynamic programming, depth-first search and trees, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Dynamic Programming, Depth-First Search, Trees
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
An undirected tree has n nodes labelled 0 to n - 1 and is rooted at node 0; edges[i] = [a, b] is an edge. Each node carries a positive value values[i]. Your score starts at 0.
In one operation you pick a node i, add values[i] to your score and set values[i] to 0. You may perform any number of operations, but afterwards the tree must stay healthy: the sum of values on every path from the root to a leaf must be non-zero.
Return the maximum score you can reach while keeping the tree healthy.
Example 1
Input: edges = [[0,1],[0,2],[0,3],[2,4],[4,5]], values = [5,2,5,2,1,1]
Output: 11
Explanation: Take every node except the root: each path still contains the root's 5. The score is 2 + 5 + 2 + 1 + 1 = 11.
Example 2
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: Leave node 1 (value 10) untaken, which protects both leaves under it, and leave the two leaves under node 2 (3 + 5 = 8, cheaper than node 2's 9). Everything else — 20 + 9 + 7 + 4 = 40 — is taken.
Example 3
Input: edges = [[0,1]], values = [3,7]
Output: 7
Explanation: One path, 0 → 1. Keep the cheaper node: take 7, leave 3.
Constraints
2 <= n <= 2 * 10^4edges.length == n - 10 <= edges[i][0], edges[i][1] < n1 <= values[i] <= 10^5 (reduced from 10^9 so the score fits a 32-bit integer)The edges form a tree
Hints for Maximum Score After Applying Operations on a Tree
Hint 1
Instead of maximising what you take, minimise what you must leave behind: score = total − (value kept).
Hint 2
A root-to-leaf path is safe as soon as one node on it is left untaken. For a subtree, either its root is left untaken (all paths through it are safe at once), or every child subtree must be made safe on its own.
Hint 3
keep(leaf) = values[leaf]; for an inner nodekeep(u) = min(values[u], Σ keep(child)). The answer istotal − keep(0).
How to solve Maximum Score After Applying Operations on a Tree
Flip the objective: maximising the taken sum is the same as minimising the untaken sum, subject to every root-to-leaf path keeping at least one untaken node (values are positive, so a path is non-zero exactly when something on it remains).
Approach
- Root the tree at 0 and get a parent-before-child order with BFS.
- Process nodes in reverse order. For a leaf (no children)
keep = values[leaf]— its own path ends there, so it must stay. - For an inner node
keep(u) = min(values[u], sum of keep over its children): either leaveuitself, which protects every path below it, or takeuand protect each child subtree separately. - Return
sum(values) − keep(0).
Why it works
Every root-to-leaf path through u continues into exactly one child subtree. Leaving u untaken protects all of them, and once that is done the cheapest choice below is to take everything. Taking u means each child subtree must protect its own paths, independently, at cost keep(child). Those are the only two options, so the minimum is exact.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- A leaf must be kept if every ancestor was taken —
keep(leaf)is its value, not 0. - The root is never a leaf here (
n ≥ 2), even when it has a single child. - Sums can pass 2^31 in the original constraints; with values up to 10^5 here they still need care in intermediate totals — keep them 64-bit.
Reference solution
Python
from typing import List
def maximumScoreAfterOperations(edges: List[List[int]], values: List[int]) -> int:
n = len(values)
adj = [[] for _ in range(n)]
for a, b in edges:
adj[a].append(b)
adj[b].append(a)
parent = [-1] * n
order = [0]
seen = [False] * n
seen[0] = True
i = 0
while i < len(order):
u = order[i]
i += 1
for v in adj[u]:
if not seen[v]:
seen[v] = True
parent[v] = u
order.append(v)
child_sum = [0] * n
has_child = [False] * n
keep = [0] * n
for u in reversed(order):
keep[u] = min(values[u], child_sum[u]) if has_child[u] else values[u]
p = parent[u]
if p >= 0:
child_sum[p] += keep[u]
has_child[p] = True
return sum(values) - keep[0]Java
public static int maximumScoreAfterOperations(int[][] edges, int[] values) {
int n = values.length;
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
int[] parent = new int[n], order = new int[n];
boolean[] seen = new boolean[n];
Arrays.fill(parent, -1);
int tail = 0;
order[tail++] = 0;
seen[0] = true;
for (int q = 0; q < tail; q++) {
int u = order[q];
for (int v : adj.get(u)) if (!seen[v]) { seen[v] = true; parent[v] = u; order[tail++] = v; }
}
long[] childSum = new long[n], keep = new long[n];
boolean[] hasChild = new boolean[n];
long total = 0;
for (int q = n - 1; q >= 0; q--) {
int u = order[q];
total += values[u];
keep[u] = hasChild[u] ? Math.min(values[u], childSum[u]) : values[u];
if (parent[u] >= 0) { childSum[parent[u]] += keep[u]; hasChild[parent[u]] = true; }
}
return (int) (total - keep[0]);
}C++
int maximumScoreAfterOperations(vector<vector<int>>& edges, vector<int>& values) {
int n = values.size();
vector<vector<int>> adj(n);
for (auto& e : edges) { adj[e[0]].push_back(e[1]); adj[e[1]].push_back(e[0]); }
vector<int> parent(n, -1), order;
vector<bool> seen(n, false);
order.push_back(0);
seen[0] = true;
for (int q = 0; q < (int) order.size(); q++) {
int u = order[q];
for (int v : adj[u]) if (!seen[v]) { seen[v] = true; parent[v] = u; order.push_back(v); }
}
vector<long long> childSum(n, 0), keep(n, 0);
vector<bool> hasChild(n, false);
long long total = 0;
for (int q = n - 1; q >= 0; q--) {
int u = order[q];
total += values[u];
keep[u] = hasChild[u] ? min((long long) values[u], childSum[u]) : values[u];
if (parent[u] >= 0) { childSum[parent[u]] += keep[u]; hasChild[parent[u]] = true; }
}
return (int) (total - keep[0]);
}JavaScript
var maximumScoreAfterOperations = function(edges, values) {
var n = values.length;
var adj = [];
for (var i = 0; i < n; i++) adj.push([]);
for (var i = 0; i < edges.length; i++) {
adj[edges[i][0]].push(edges[i][1]);
adj[edges[i][1]].push(edges[i][0]);
}
var parent = new Array(n).fill(-1), seen = new Array(n).fill(false), order = [0];
seen[0] = true;
for (var q = 0; q < order.length; q++) {
var u = order[q];
for (var j = 0; j < adj[u].length; j++) {
var v = adj[u][j];
if (!seen[v]) { seen[v] = true; parent[v] = u; order.push(v); }
}
}
var childSum = new Array(n).fill(0), hasChild = new Array(n).fill(false), keep = new Array(n).fill(0);
var total = 0;
for (var q = n - 1; q >= 0; q--) {
var u = order[q];
total += values[u];
keep[u] = hasChild[u] ? Math.min(values[u], childSum[u]) : values[u];
if (parent[u] >= 0) { childSum[parent[u]] += keep[u]; hasChild[parent[u]] = true; }
}
return total - keep[0];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 402 dynamic programming problems · the whole catalogue
Learn the technique: Dynamic Programming · Depth-First Search (DFS)