Show problems as
Classic problem #2603HardArrayTreeGraph TheoryTopological Sort

Collect Coins in a Tree

Real-world version: Shortest Round Trip to Sweep Every Parcel
Tracked in this browser only
Read Collect Coins in a Tree on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A network of hubs is given as a tree: edges lists the links, and coins[i] is 1 when hub i holds a parcel and 0 otherwise.

A van starts at any hub it likes and must finish back where it started. A parcel is swept when the van visits some hub no more than two links away from the parcel's hub.

Every link travelled counts, and travelling the same link again counts again. Return the fewest links the round trip can travel while sweeping every parcel.

Examples

Example 1

Input
coins = [1, 0, 0, 1], edges = [[0, 1], [1, 2], [2, 3]]
Output
0

The hubs run in a line of four with parcels at the two ends. Standing at either middle hub sweeps both ends, since each is within two links, so the van need not move at all.

Example 2

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

The line is eight hubs long with parcels at the ends. The van must reach within two links of each end, which means covering the two middle links and walking them both ways.

Example 3

Input
coins = [0], edges = []
Output
0

A single hub with no parcel means there is nothing to sweep.

Constraints

  • 1 <= coins.length <= 3 * 10^4
  • 0 <= coins[i] <= 1
  • edges.length == coins.length - 1
  • edges[i].length == 2
  • 0 <= edges[i][0] <= coins.length - 1
  • 0 <= edges[i][1] <= coins.length - 1
  • The two hubs on a link are different
  • The links form a tree

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def collect_the_coins(coins: list[int], edges: list[list[int]]) -> int:
Java
public int collectTheCoins(int[] coins, int[][] edges)

More on the same topics