Maximum Score After Applying Operations on a Tree

Medium
1644.

Maximum Score After Applying Operations on a Tree

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.

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^4
  • edges.length == n - 1
  • 0 <= edges[i][0], edges[i][1] < n
  • 1 <= values[i] <= 10^5 (reduced from 10^9 so the score fits a 32-bit integer)
  • The edges form a tree
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} edges
 * @param {number[]} values
 * @return {number}
 */
var maximumScoreAfterOperations = function(edges, values) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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^4
  • edges.length == n - 1
  • 0 <= edges[i][0], edges[i][1] < n
  • 1 <= 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

  1. Hint 1

    Instead of maximising what you take, minimise what you must leave behind: score = total − (value kept).

  2. 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.

  3. Hint 3

    keep(leaf) = values[leaf]; for an inner node keep(u) = min(values[u], Σ keep(child)). The answer is total − 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

  1. Root the tree at 0 and get a parent-before-child order with BFS.
  2. Process nodes in reverse order. For a leaf (no children) keep = values[leaf] — its own path ends there, so it must stay.
  3. For an inner node keep(u) = min(values[u], sum of keep over its children): either leave u itself, which protects every path below it, or take u and protect each child subtree separately.
  4. 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)