Maximum Score After Applying Operations on a Tree
Source: leetcode
Difficulty: Medium
Tags: dynamic-programming, tree, depth-first-search

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


You are also given a **0\-indexed** integer array `values` of length `n`, where `values[i]` is the **value** associated with the `ith` node.


You start with a score of `0`. In one operation, you can:


- Pick any node `i`.
- Add `values[i]` to your score.
- Set `values[i]` to `0`.


A tree is **healthy** if the sum of values on the path from the root to any leaf node is different than zero.


Return *the **maximum score** you can obtain after performing these operations on the tree any number of times so that it remains **healthy**.*


 


**Example 1:**


![](https://assets.leetcode.com/uploads/2023/10/11/graph-13-1.png)

```

Input: edges = [[0,1],[0,2],[0,3],[2,4],[4,5]], values = [5,2,5,2,1,1]
Output: 11
Explanation: We can choose nodes 1, 2, 3, 4, and 5. The value of the root is non-zero. Hence, the sum of values on the path from the root to any leaf is different than zero. Therefore, the tree is healthy and the score is values[1] + values[2] + values[3] + values[4] + values[5] = 11.
It can be shown that 11 is the maximum score obtainable after any number of operations on the tree.

```

**Example 2:**


![](https://assets.leetcode.com/uploads/2023/10/11/graph-14-2.png)

```

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 can choose nodes 0, 2, 3, and 4.
- 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 3 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.
Therefore, the tree is healthy and the score is values[0] + values[2] + values[3] + values[4] = 40.
It can be shown that 40 is the maximum score obtainable after any number of operations on the tree.

```

 


**Constraints:**


- `2 <= n <= 2 * 104`
- `edges.length == n - 1`
- `edges[i].length == 2`
- `0 <= ai, bi < n`
- `values.length == n`
- `1 <= values[i] <= 109`
- The input is generated such that `edges` represents a valid tree.




C++ solution:
class Solution {
public:

    //subtree => {所有path至少都有一個點不存在,所有點都存在}
    pair<long long,long long> Dynamicprogramming(vector<vector<int>>& adj, vector<unsigned char>& visited, vector<int>& values, int index) {
        visited[index] = 1;

        bool hasChild = false;
        long long atleast1 = 0, total = 0;
        pair<long long,long long> result;
        for(int child : adj[index]) {
            if(visited[child] == 0) {
                result = Dynamicprogramming(adj, visited, values, child);
                atleast1 += result.first;
                total += result.second;
                hasChild = true;
            }
        }

        //base case:
        if(hasChild == false) {
            //cout << "base => index: " << index << endl;
            return {0, values[index]};
        }  

        //cout << "index: " << index << " atleast1: " << atleast1 << " total: " << total << endl; 
        if(index != 0)
            return {max(total, values[index] + atleast1), values[index] + total};
        else
            return {total, values[index] + atleast1};
    }

    //這題題意上不是很好理解,簡單來說就是可以在tree上取走一些節點.
    //但有個前提就是拿走的這些節點,不能造成Path的sum變為0.
    //然後在這個前提之下,想辦法拿到最多加總值的節點
    //所以很明顯得用DP去解,且滿足兩個條件.
    //1.節點可決定取或不取
    //2.想辦法找出max value
    //subtree => {所有path至少都有一個點不存在,所有點都存在}
    //root => max((root->val + 至少一個點不存在), 所有點都存在);
    long long maximumScoreAfterOperations(vector<vector<int>>& edges, vector<int>& values) {
        ios_base::sync_with_stdio(0);
        cin.tie(NULL);
        cout.tie(NULL);

        int limit = values.size(), edges_limit = edges.size();
        //1.先create雙向相鄰串列和visted array;
        vector<vector<int>> adj(limit);
        vector<unsigned char> visited(limit);
        for(int i = 0; i < edges_limit; ++i) {
            int u = edges[i][0], v = edges[i][1];
            adj[u].push_back(v);
            adj[v].push_back(u);
        }

        //2.create Dynamic programming的DFS for all path and return answer
        //  max((root->val + 所有路徑至少有一點不存在)),所有點都存在)
        pair<long long,long long> result = Dynamicprogramming(adj, visited, values, 0);
        return max(result.first, result.second);
    }
};

Go solution:
var path map[int][]int

func maximumScoreAfterOperations(edges [][]int, values []int) int64 {
	path = make(map[int][]int)
	// init the graph
	for i := range edges {
		if path[edges[i][0]] == nil {
			path[edges[i][0]] = make([]int, 0)
		}
		if path[edges[i][1]] == nil {
			path[edges[i][1]] = make([]int, 0)
		}
		path[edges[i][0]] = append(path[edges[i][0]], edges[i][1])
		path[edges[i][1]] = append(path[edges[i][1]], edges[i][0])
	}
	// run solver function
	result, _ := solver(0, values, -1)
	return result
}

//solve is a dfs function to determinate score and cost for each path
func solver(index int, values []int, parent int) (score int64, cost int64) {
	for i := range path[index] {
		if path[index][i] == parent {
			continue
		}
		pathScore, pathCost := solver(path[index][i], values, index)
		// sum all score and cost for each path
		score += pathScore
		cost += pathCost
	}
	// if cost is 0 that mean the node is leaf return score = 0 and the values as the cost
	if cost == 0 {
		return 0, int64(values[index])
	}

	// check if the current root is less than minCost 
	if int64(values[index]) < cost{
		// if current value less than minCost then return root as minCost
		// and return maxScore = maxScore + minCost
		return score + cost, int64(values[index])
	}
	// else add the current node value to score
	return score + int64(values[index]), cost
}

Java solution:
class Solution {
    public long dfs(int i, List<Integer>[] adj, int[] v, int[] vis) {
        if (adj[i].size() == 1 && i != 0)
            return (long) v[i];
        long s = 0;
        vis[i] = 1;
        for (int j : adj[i]) {
            if (vis[j] == 1)
                continue;
            s += dfs(j, adj, v, vis);
        }
        return Math.min((long) v[i], s);
    }

    public long maximumScoreAfterOperations(int[][] edges, int[] values) {
        int n = values.length;
        List<Integer>[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int i = 0; i < n - 1; i++) {
            adj[edges[i][0]].add(edges[i][1]);
            adj[edges[i][1]].add(edges[i][0]);
        }
        long s = 0;
        for (int i : values)
            s += i;
        int[] vis = new int[n];
        long k = dfs(0, adj, values, vis);
        return s - k;
    }
}

JavaScript solution:
/**
 * @param {number[][]} edges
 * @param {number[]} values
 * @return {number}
 */
var maximumScoreAfterOperations = function (edges, values) {
    let n = edges.length;
    let map = new Array(n + 1).fill().map((_) => []);
    for (let [a, b] of edges) {
        map[a].push(b);
        map[b].push(a);
    }

    const dfs = function (root, parent) {
        let value = values[root];
        let childSum = 0;
        for (let child of map[root]) {
            if (child === parent) continue;
            childSum += dfs(child, root);
        }
        return childSum === 0 || value < childSum ? value : childSum;
    }

    return values.reduce((acc, num) => acc + num, 0) - dfs(0, -1);
};

Python solution:
class Solution:
    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:
        n = len(edges)+1
        adj = [[] for _ in range(n)]
        for a, b in edges:
            adj[a].append(b)
            adj[b].append(a)

        def dfs(i, p):
            # returns result_if_healthy_ancestor, result_if_no_healthy_ancestor
            if len(adj[i]) == 1 and i != 0:
                # if leaf node, exit early
                return values[i], 0
            if_healthy_ancestor = 0
            if_no_healthy_ancestor = 0
            for j in adj[i]:
                if j == p:
                    continue
                sub_healthy, sub_no_healthy = dfs(j, i)
                if_healthy_ancestor += sub_healthy
                if_no_healthy_ancestor += sub_no_healthy
            return values[i]+if_healthy_ancestor, max(if_healthy_ancestor, values[i]+if_no_healthy_ancestor)
        
        return dfs(0, -1)[1]

Ruby solution:
# @param {Integer[][]} edges
# @param {Integer[]} values
# @return {Integer}
def maximum_score_after_operations(edges, values)
  @values = values
  @tree = Array.new(@values.size) { [] }
  edges.each do |u, v|
    @tree[u] << v
    @tree[v] << u
  end

  recorrido(0, -1).min
end

def recorrido(node, parent)
  max_val = 0
  sum = 0
      
  @tree[node].each do |i|
    next if i == parent
    
    branch = recorrido(i, node)
    max_val += branch[0]
    sum += branch[1]
  end
  
  max_val += @values[node] if @tree[node] != [parent]
  
  [[max_val, sum].max, sum + @values[node]]
end