# 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的结果呢

因为```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

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};
}
}