---
# System prepended metadata

title: 2378. Choose Edges to Maximize Score in a Tree
tags: [Leetcode, DFS, Medium]

---

# 2378. Choose Edges to Maximize Score in a Tree
###### tags: `Leetcode` `Medium` `DFS`
Link: https://leetcode.com/problems/choose-edges-to-maximize-score-in-a-tree/description/
## 思路
先建图 然后对每一个点做dfs 找到包含这个点的maximum score和不包含这个点的maximum score
最终答案就是包含```root```的max score和不包含```root```的max score取最大值
那么如何计算每个dfs的结果呢 
```without_root```我们只需要把它的所有children的```with_root```和```without_root```的最大值加在一起即可
因为```with_root = max(weight of (root, a) - without_a + with_a + without_root)```(```a```是```root```的child)
我们需要找到一条从```root```出来的边```(root, child)```, ```weight of (root, child) - without_a + with_a + without_root```最大
## Code
```java=
class Solution {
    public long maxScore(int[][] edges) {
        int root = 0;
        List<List<int[]>> graph = new ArrayList<>();
        for(int i=0; i<edges.length; i++) graph.add(new ArrayList<>());
        for(int i=0; i<edges.length; i++){
            int[] edge = edges[i];
            if(edge[0]!=-1) graph.get(edge[0]).add(new int[]{i, edge[1]});
        }
        long[] ans = dfs(root, graph);
        return Math.max(ans[0], ans[1]);
    }
    public long[] dfs(int root, List<List<int[]>> graph){
        long with_root = 0L, without_root = 0L;
        for(int[] next:graph.get(root)){
            long[] tmp = dfs(next[0], graph);
            without_root += Math.max(tmp[0], tmp[1]);
            with_root = Math.max(with_root, next[1]-tmp[0]+tmp[1]);
        }
        with_root += without_root;
        return new long[]{with_root, without_root};
    }
}
```