#2603

Collect Coins in a Tree

master · 1715 · lc hard +32 · verified · 39.7% accepted · 558 likes · top 19%

Description

An undirected, unrooted tree has n nodes indexed 0 to n - 1. Each node may hold a coin (coins[i] = 1). Starting from any node, you can either collect all coins within distance 2 or move to an adjacent node. Find the minimum edge traversals needed to collect all coins and return to the starting node. Each traversal of an edge counts, even if repeated.

Example 1:

Input: coins = [1,0,0,0,0,1], edges = [[0,1],[1,2],[2,3],[3,4],[4,5]]

Output: 2

Explanation: Start at vertex 2, collect the coin at vertex 0, move to vertex 3, collect the coin at vertex 5 then move back to vertex 2.

Example 2:

Input: coins = [0,0,0,1,1,0,0,1], edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[5,6],[5,7]]

Output: 2

Explanation: Start at vertex 0, collect the coins at vertices 4 and 3, move to vertex 2, collect the coin at vertex 7, then move back to vertex 0.

Code

1

2

3

class Solution:
    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:

class Solution:
    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int: