872. Coin Collector Tree
A cleanup robot works in a park whose n clearings (numbered 0 to n - 1) are joined by n - 1 paths forming a tree, given as edges[i] = [a, b]. Clearing i holds a coin when coins[i] = 1. The robot may begin at any clearing. From wherever it stands it can pick up every coin that is at most two paths away, and it can repeat this after each move along a path. When it has collected every coin it must be back at the clearing where it started.
Return the minimum number of path traversals needed. If the park holds no coins, the answer is 0.
Example 1
- Input:
- coins = [0,1,0,0,0,0,0,1]edges = [[0,1],[0,2],[0,3],[3,4],[4,5],[5,6],[6,7]]
- Output:
- 4
- Explanation:
Start at clearing 3: the coin at 1 is two paths away (3-0-1), and after walking 3-4-5 the coin at 7 is two paths away; walking back to 3 makes 4 traversals, and fewer cannot reach both far-apart coins.
Example 2
- Input:
- coins = [0,0,0,0,0,0,0,1]edges = [[0,1],[0,2],[0,3],[3,4],[4,5],[5,6],[6,7]]
- Output:
- 0
- Explanation:
Start at clearing 5: the only coin, at clearing 7, is two paths away, so the robot does not need to move at all and the answer is 0.
Constraints
- 1 ≤ n = coins.length ≤ 105
- coins[i] is 0 or 1
edges.length == n - 1, 0 ≤ a, b < n and the paths form a tree
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 400 msC++ 100 msJava 200 msJavaScript 200 msTypeScript 200 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)