914. Minimum Time to Collect All Apples

Given an undirected tree with n nodes labeled 0..n-1 (edges as pairs) and a boolean list hasApple marking which nodes hold an apple, you start at node 0 and must collect every apple and return to node 0. Each edge takes 1 second to traverse in each direction. Return the minimum total seconds. The input is JSON {n, edges, hasApple}.

Input: JSON {n, edges, hasApple}.

Output: Integer — the minimum seconds.

Examples

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: Visit the apple-bearing subtrees and return.

Input: {"n":1,"edges":[],"hasApple":[false]}
Output: 0
Explanation: No apples, no travel.

Input: {"n":2,"edges":[[0,1]],"hasApple":[false,true]}
Output: 2
Explanation: Go to node 1 and back.

Constraints

• 1<=n<=10^5
• edges form a tree

Asked by