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

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

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/04/23/min_time_collect_apple_1.png" style="width: 300px; height: 212px;" />
<pre>
<strong>Input:</strong> n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,true,true,false]
<strong>Output:</strong> 8 
<strong>Explanation:</strong> 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.  
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/04/23/min_time_collect_apple_2.png" style="width: 300px; height: 212px;" />
<pre>
<strong>Input:</strong> n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,false,true,false]
<strong>Output:</strong> 6
<strong>Explanation:</strong> 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.  
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,false,false,false,false,false]
<strong>Output:</strong> 0
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>edges.length == n - 1</code></li>
	<li><code>edges[i].length == 2</code></li>
	<li><code>0 &lt;= a<sub>i</sub> &lt; b<sub>i</sub> &lt;= n - 1</code></li>
	<li><code>hasApple.length == n</code></li>
</ul>

class Solution:
    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:
        
        vex2nbs = defaultdict(list)
        for e in edges:
            vex2nbs[e[0]].append(e[1])
            vex2nbs[e[1]].append(e[0])
        apples = set([i for i in range(len(hasApple)) if hasApple[i]])
        # print(vex2nbs, apples)
        if len(vex2nbs) == 0 or len(apples) == 0:
            return 0
        visited = set()
        def dfs(vex): # min time of picking apples of the subtree
            visited.add(vex)
            nbs = vex2nbs[vex]
            ans = 0
            for nb in nbs:
                if nb in visited:
                    continue
                time = dfs(nb)
                # print(vex, nb, val)
                if time != 0 or nb in apples:
                    ans += (time+2)
            return ans
        return dfs(0)

# time o(n), space o(n)

""" bfs is not working
        vex2nbs = defaultdict(list)
        for e in edges:
            vex2nbs[e[0]].append(e[1])
            vex2nbs[e[1]].append(e[0])

        pos = set([i for i in range(len(hasApple)) if hasApple[i]])
        if len(pos) == 0 or (len(pos) == 1 and pos[0]==0):
            return 0
        def verify(arr):
            for el in pos:
                if el not in arr:
                    return False
            return True
        
        min_len = float('inf')
        qu = deque()
        for el in vex2nbs[0]:
            qu.append([0, el])
        visited = set((tuple(el) for el in qu))
        while qu:
            print(qu)
            vexs = qu.popleft()
            for v in vex2nbs[vexs[-1]]:
                if (vexs[-1], v) not in visited:
                    visited.add((vexs[-1], v))
                    new_vexs = vexs + [v]
                    if v == 0 and verify(new_vexs):
                        min_len = min(min_len, len(new_vexs))
                    qu.append(new_vexs)  
        return min_len
"""

61209