Show problems as
Classic problem #1443MediumHash TableTreeDepth-First SearchBreadth-First SearchDP on Trees

Minimum Time to Collect All Apples in a Tree

Real-world version: Visiting Every Marked Junction and Returning
Tracked in this browser only
Read Minimum Time to Collect All Apples 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 n junctions numbered 0 through n - 1 is joined by the pipes pipes, one fewer pipe than there are junctions, with every junction reachable from every other and no loop anywhere. Walking a pipe takes one second, either way.

marked[i] says whether junction i needs visiting.

Start at junction 0, visit every marked junction, and return to junction 0. Return the fewest seconds it takes.

Examples

Example 1

Input
n = 4, pipes = [[0, 1], [1, 2], [0, 3]], marked = [false, false, true, false]
Output
4

Only junction 2 is marked, and reaching it means walking two pipes out and the same two back. The pipe to junction 3 has nothing marked beyond it and is never walked.

Example 2

Input
n = 3, pipes = [[0, 1], [0, 2]], marked = [false, true, true]
Output
4

Both junctions hanging off the start are marked, so each of the two pipes is walked out and back.

Example 3

Input
n = 1, pipes = [], marked = [true]
Output
0

The one junction is where the walk starts, so it is already visited and nothing needs walking.

Constraints

  • 1 <= n <= 10^5
  • pipes.length == n - 1
  • pipes[i].length == 2
  • 0 <= pipes[i][j] <= n - 1
  • The two ends of a pipe are different junctions.
  • marked.length == n

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 min_time(n: int, pipes: list[list[int]], marked: list) -> int:
Java
public int minTime(int n, int[][] pipes, boolean[] marked)

More on the same topics