1443. Minimum Time to Collect All Apples in a Tree

Link

Solution

有想到build graph

但怎麼推演沒想出來

有想到回傳直是該node為root的結果

 public int minTime(int n, int[][] edges, List<Boolean> hasApple) {
        List<Integer>[] graph = new List[n];
        for(int i = 0; i < n; i++) graph[i] = new ArrayList<>();
        for(int[] edge : edges){
            graph[edge[0]].add(edge[1]);
            graph[edge[1]].add(edge[0]);
        }
        boolean[] isVisited = new boolean[n];
        
        return dfs(graph, hasApple, isVisited, 0);
    }
    
    public int dfs(List<Integer>[] graph, List<Boolean> hasApple, boolean[] isVisited, int index){
        
        if(isVisited[index]) return 0;
        
        isVisited[index] = true;
        
        int ret = 0;
        
        //這段loop沒想出來
        for(int next : graph[index]){
            ret += dfs(graph, hasApple, isVisited, next);
        }
        
        if(index != 0 && (ret > 0 || hasApple.get(index))) ret += 2;
        
        return ret;
    }