Maximum Score After Applying Operations on a Tree

A more efficient approach uses dynamic programming on the tree. The key insight is to reframe the problem: instead of maximizing the score of nodes we take, we can minimize the sum of values of nodes we don't take. The 'healthy' condition requires that on every path from the root to a leaf, at least one node's value must be left untouched.

This structure lends itself to a post-order traversal (DFS) where for each node, we compute the minimum value that must be left in its subtree to satisfy the healthy condition for all paths starting from that node. This avoids re-computation and explores the decision space efficiently.

• The problem of maximizing the score of taken nodes is equivalent to minimizing the sum of values of nodes that are left untouched, subject to the 'healthy' constraint.
• The healthy constraint means that for every root-to-leaf path, at least one node must be left untouched.
• We can define a function, minCost(u), which represents the minimum sum of values we must leave in the subtree rooted at u to ensure all paths from u to leaves within its subtree are 'healthy'.
• We can compute minCost(u) using a post-order traversal (DFS).
• Base Case: For a leaf node u, the only path in its subtree is the node itself. To make this path healthy, we must leave values[u]. So, minCost(u) = values[u].
• Recursive Step: For an internal node u, we have two choices:
  1. Leave values[u]. The cost is values[u]. This satisfies the condition for all paths from u downwards.
  2. Take values[u]. Now, for each child v of u, we must satisfy the condition within v's subtree. The total cost for this choice is the sum of minCost(v) for all children v.
• The recurrence relation is minCost(u) = min(values[u], sum(minCost(v) for v in children(u))).
• First, calculate the total sum of all values in the tree.
• Then, run the DFS from the root (node 0) to compute minCost(0).
• The final maximum score is totalSum - minCost(0).

We can solve this problem optimally in linear time using a single DFS traversal. Let's define dfs(u, p) as a function that computes the minimum sum of values that must be left in the subtree rooted at u (with p being its parent) to ensure that any path from u to a leaf in its subtree has a non-zero sum.

• For a leaf node u: The only path is the node itself. We must leave its value. So, dfs(u, p) returns values[u].
• For an internal node u: We have two options:
  1. Leave values[u]: The cost incurred is values[u]. Since u is on every path starting from itself, this single choice makes all paths from u to its descendant leaves healthy.
  2. Take values[u]: We don't leave values[u]. To maintain the healthy property, we must now ensure it's satisfied in the subtrees of its children. Since the subtrees are independent, we must pay the minimum cost for each child's subtree. The total cost is the sum of the results of dfs(v, u) for all children v of u.

We choose the option with the minimum cost. Thus, for an internal node u, dfs(u, p) = min(values[u], sum(dfs(v, u))) for all children v.

The final answer is the total sum of all values in the tree minus the minimum cost for the entire tree, which is dfs(0, -1).

import java.util.ArrayList; 
import java.util.List;

class Solution {
    private List<List<Integer>> adj;
    private int[] values;

    public long maximumScoreAfterOperations(int[][] edges, int[] values) {
        int n = values.length;
        this.adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }
        this.values = values;

        long totalSum = 0;
        for (int value : values) {
            totalSum += value;
        }

        long minUnpickedSum = dfs(0, -1);
        return totalSum - minUnpickedSum;
    }

    /**
     * Computes the minimum sum of values to leave in the subtree of u
     * to make all paths from u to its leaves healthy.
     */
    private long dfs(int u, int p) {
        long childrenSubtreeMinSum = 0;
        boolean isLeaf = true;

        for (int v : adj.get(u)) {
            if (v != p) {
                isLeaf = false;
                childrenSubtreeMinSum += dfs(v, u);
            }
        }

        // Base case: if the node is a leaf in the rooted tree traversal.
        if (isLeaf) {
            return (long)values[u];
        }

        // Recursive step: for an internal node, choose the minimum of two options.
        return Math.min((long)values[u], childrenSubtreeMinSum);
    }
}