1203. Minimum Time to Collect All Apples

Given an undirected tree with n nodes (0 to n-1) rooted at 0, described by edges, and a boolean list hasApple, you traverse edges (each edge costs 2 seconds round-trip) starting and ending at node 0. Return the minimum time to collect every apple. The input is JSON {n, edges, hasApple}.

Input: JSON {n, edges, hasApple}.

Output: Integer — the minimum collection time.

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 branches.

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
Explanation: No apples.

Input: {"n":2,"edges":[[0,1]],"hasApple":[false,true]}
Output: 2
Explanation: One round trip.

Constraints

• 1<=n<=10^5

Asked by