Given an undirected tree consisting of n vertices numbered from 0 to n-1, which has some apples in their vertices. You spend 1 second to walk over one edge of the tree. Return the minimum time in seconds you have to spend to collect all apples in the tree, starting at vertex 0 and coming back to this vertex.

The edges of the undirected tree are given in the array edges, where edges[i] = [ai, bi] means that exists an edge connecting the vertices ai and bi. Additionally, there is a boolean array hasApple, where hasApple[i] = true means that vertex i has an apple; otherwise, it does not have any apple.

&nbsp;
Example 1:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,true,true,false]
Output: 8 
Explanation: The figure above represents the given tree where red vertices have an apple. One optimal path to collect all apples is shown by the green arrows.  


Example 2:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,false,true,false]
Output: 6
Explanation: The figure above represents the given tree where red vertices have an apple. One optimal path to collect all apples is shown by the green arrows.  


Example 3:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,false,false,false,false,false]
Output: 0


&nbsp;
Constraints:


	1 &lt;= n &lt;= 105
	edges.length == n - 1
	edges[i].length == 2
	0 &lt;= ai &lt; bi &lt;= n - 1
	fromi &lt; toi
	hasApple.length == n


class Solution:

    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:
        graph_map = {i: set() for i in range(n)}
        for edge in edges:
            graph_map[edge[0]].add(edge[1])
            graph_map[edge[1]].add(edge[0])

        self.result = set()
        visited = set()
        def dfs(node, path):
            visited.add(node)
            if hasApple[node]:
                temp = path + '|' + str(node)
                temp = temp.split('|')[1:]
                # print(temp)
                for i in range(1, len(temp)):
                    self.result.add((temp[i], temp[i-1]))
            for nei in graph_map[node]:
                if nei not in visited:
                    dfs(nei, path + '|' + str(node))

        dfs(0, "")
        # print(self.result)
        return len(self.result) * 2
class Solution {
    public int minTime(int n, int[][] edges, List<Boolean> hasApple) {
        HashMap<Integer,List<Integer>> graph = new HashMap<>(n);
        for(int edge[] : edges){
            int a = edge[0], b = edge[1];
            graph.putIfAbsent(a, new LinkedList<>());
            graph.putIfAbsent(b, new LinkedList<>());
            graph.get(a).add(b);
            graph.get(b).add(a);
        }
        
        boolean[] visited = new boolean[n];
        Arrays.fill(visited,false);
        
        int a = move(0,graph,hasApple,n,visited);
        
        return a==-1?0:a;
    }
                
    public int move(int i,HashMap<Integer,List<Integer>> graph,List<Boolean> hasApple,int n,boolean[] visited){
        visited[i]=true;
        boolean cont = false;
        if(hasApple.get(i)){
            cont=true;
        }
        
        List<Integer> list = graph.get(i);
        
        if(list==null){
            return cont?0:-1;
        }
        int j = 0;
        for(int k : list){
            if(!visited[k]){
                int a = move(k,graph,hasApple,n,visited);
                if(a!=-1){
                    j+=2+a;
                }
            }
        }
        if(j==0 && cont) return 0;
        return j==0?-1:j;
    }
}
class DSU{
private:
    vector<int> parent,rank ;
public:
    DSU(int n){
        rank.resize(n,1) ;
        parent.resize(n) ;
        iota(begin(parent),end(parent),0) ;
    }

    int find_parent(int node){
        if(node == parent[node]) return node ;
        return parent[node] = find_parent(parent[node]) ;
    }
    void Union(int u , int v){
        int U = find_parent(u) , V = find_parent(v) ;
        if(U == V) return ;
        if(rank[U] < rank[V]) swap(U,V) ;
        rank[U] += rank[V] ;
        parent[V] = U ;
    }
    int getRank(int node){
        return rank[parent[node]] ;
    }

};

class Solution {
public:
    vector<bool> dp ;
    vector<bool> hasApple ;
    vector<int> adj[100001] ;
    vector<int> visited ;

    void dfs(int src){
        visited[src] = 1 ;
        for(auto &nbr : adj[src]){
            if(!visited[nbr]){
                dfs(nbr) ;
                dp[src] = dp[src] or dp[nbr] ;
            }
        }
    }

    int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) {
        DSU dsu(n) ;
        dp = hasApple ; visited.resize(n,0) ; this->hasApple = hasApple ;

        for(auto &x : edges) adj[x[0]].push_back(x[1]) , adj[x[1]].push_back(x[0]) ;
        dfs(0) ;

        int start = -1 ;
        for(int i = 0 ; i < n ; ++i ){
            if(!dp[i]) continue ;
            if(start == -1){
                start = i ; continue ;
            }
            dsu.Union(start,i) ;
        }

        return (dsu.getRank(0) - 1) * 2 ;
    }
};
    var cnvrtAdjLst = (mat) => {//converts the list of edges to adjacency list
    let map = new Map();
    for(let i=0; i<mat.length; i++){
        let [p,c] = mat[i];
        if(map[p]===undefined) map[p] = [c];
        else map[p].push(c);

        if(map[c]===undefined) map[c] = [p];
        else map[c].push(p);
    }
    return map;
}
var minTime = function(n, edges, hasApple) {
    let adjList = cnvrtAdjLst(edges);//convert to adjacency list for undirected graph
    let visited = new Set();// visited set for checking trivial loop
    let dfsForApples = (src, len) => {
        visited.add(src);// add root to visited set, as we start exploring the subtree
        let lengthFromNow = 0;//total length of path visited by each child, 0 if no child has apple
        for(let i in adjList[src]){
            if(!visited.has(adjList[src][i])){
                lengthFromNow += dfsForApples(adjList[src][i],len+1);// add child path length to total length
            }

        }
        if(lengthFromNow>0){
            //if there is an apple present in the subtree
            return lengthFromNow + 2;
        }
        else if(hasApple[src]){
            //if there is no apple in subtree but apple is present on the root node
            return 2;
        }
        else{
            // if no apple is present in subtree
            return 0;
        }
    }
    visited.add(0);
    let res = dfsForApples(0,0);
    return res?res-2:0;//check if the root node itself has an apple or no apple is present
};
Minimum Time to Collect All Apples in a Tree