2925. Maximum Score After Applying Operations on a Tree

T: O(n)

S: O(n)

```java
class Solution {
    public long maximumScoreAfterOperations(int[][] edges, int[] values) {
        Map<Integer, List<Integer>> graph = buildGraph(edges);
        long total = 0;
        for (int num : values) {
            total += num;
        }
        return total - dfs(graph, 0, -1, values); // ans is total - min
    }
    private long dfs(Map<Integer, List<Integer>> graph, int current, int parent, int[] values) {
        if (graph.get(current).size() == 1 && graph.get(current).get(0) == parent) {
            //System.out.println("leaf:" + values[current]);
            return values[current];
        }

        long subTreeSum = 0;
        if (graph.containsKey(current)) {
            for (int next : graph.get(current)) {
                if (next == parent) {
                    continue;
                }
                subTreeSum += dfs(graph, next, current, values); // just find subtree sum
                // 2 + 2 + 1 = 5
            }
        }
        //System.out.println("subTreeSum:" + subTreeSum + ", values[current]:" + values[current]);
        return Math.min(subTreeSum, values[current]); // return min(subTreeSum, current node value)
        // this the min value in subtree
        // if we have 3 subtree, -> it's 2 + 1 + 2 = 5
    }
    private Map<Integer, List<Integer>> buildGraph(int[][] edges) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int[] edge : edges) {
            int from = edge[0];
            int to = edge[1];
            graph.putIfAbsent(from, new ArrayList<>());
            graph.get(from).add(to);

            graph.putIfAbsent(to, new ArrayList<>());
            graph.get(to).add(from);
        }
        return graph;
    }
}

/**
choose current node, or suntree sum

this the min value in subtree
if we have 3 subtree, -> it's 2 + 1 + 2 = 5


leaf:2
leaf:1
subTreeSum:1, values[current]:1
subTreeSum:1, values[current]:5
leaf:2
subTreeSum:5, values[current]:5

ex1
     at last
        5
       / \  \
       2. 1. 2
       so in these 3 subtree, min value is 2, 1, 2, and their sum = 5, 
       compare with root = min (5, 5), so return 5
       entire tree's min is 5 -> so total(16) - 5 = 11
in this way, actually we only remove a node in each path... (this one is hard to figure out...)

actually easy to under stand, because we only find "one" min in each subtree, this min can in each path


 x     if this is the min
/ \
y z. -> if these 2 are min

anyway, which one we choose...it's the remove only one node n each path

所以只要比 current node 和 childs sub tree, 就可以滿足...移除某 path 上某一 node
 

題目的意思選了後要把那個node設為0, 所以我們並不能全選, 要在root to leaf path上還是有點沒選過(這就是我們做的min node)
trcky的部分就是為什麼 選 min(root or 選子樹) 就可以是 "所有" root to leaf path 上的一點...
我想是因為... subproblem 

如果 root < 子樹 ... 假設這個 root 是全部最小的
也就是說下一次這個 root變成下一次的子樹... 那還是只會有這個 min一個


所以結論是每個子樹會有一個 min


ex2: 

      root
    /.     \
  subtree1  subtree2 
會有兩個 min (root = 20 > (subtree1 + subtree2) )


ex1: 

    因為min發生在 root -> 所以就只有一個min

    root
    /\ \




保證路徑上有一個 min 要馬就是root...要馬就是其它子樹的某個root...這樣就可以保證有"1個", 所以目標就是 find min 
->

We need to start considering elements from the leaf nodes. 
We have to leave ""at least one node in a path"" from parent to leaf.

At each root we have two options ( we will take the larger one ofcourse ) -> find min
1. either take the root and leave the child nodes ( or already leftout nodes) or
2. take the child nodes (or leftout values ) and leave the root node

```
 */
```