Tap here to switch tabs
Problem
Submissions

Problem: Collect Coins in a Tree

Collect Coins in a Tree gives an unrooted tree and a binary coin array. Choose a starting node, collect coins within two edges, and return the minimum travel needed to collect them all.

Statement

You are given an undirected, unrooted tree with n nodes indexed from 00 to n−1n - 1. The tree structure is defined by a 22D integer array edges of length n−1n - 1, where edges[i] = [a_i, b_i] indicates an undirected edge between nodes a_i and b_i. You are also given a binary array coins of size n, where coins[i] is either 00 or 11, and a value of 11 means node i contains a coin.

You may begin at any node in the tree and repeatedly perform the following operations in any order:

  • Collect all coins located at a distance of at most 22 from your current node, or

  • Move to any directly adjacent node in the tree.

Return the minimum number of edges you must traverse to collect every coin and return to your starting node.

Note: If the same edge is traversed multiple times, each traversal counts separately toward the total.

Constraints:

  • n == coins.length

  • 1≤1 \leq n ≤3×104\leq 3 \times 10^4

  • 0≤0 \leq coins[i] ≤1\leq 1

  • edges.length == n - 1

  • edges[i].length == 2

  • 0≤0 \leq a_i, b_i << n

  • a_i != b_i

  • edges represents a valid tree.

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Collect Coins in a Tree

Collect Coins in a Tree gives an unrooted tree and a binary coin array. Choose a starting node, collect coins within two edges, and return the minimum travel needed to collect them all.

Statement

You are given an undirected, unrooted tree with n nodes indexed from 00 to n−1n - 1. The tree structure is defined by a 22D integer array edges of length n−1n - 1, where edges[i] = [a_i, b_i] indicates an undirected edge between nodes a_i and b_i. You are also given a binary array coins of size n, where coins[i] is either 00 or 11, and a value of 11 means node i contains a coin.

You may begin at any node in the tree and repeatedly perform the following operations in any order:

  • Collect all coins located at a distance of at most 22 from your current node, or

  • Move to any directly adjacent node in the tree.

Return the minimum number of edges you must traverse to collect every coin and return to your starting node.

Note: If the same edge is traversed multiple times, each traversal counts separately toward the total.

Constraints:

  • n == coins.length

  • 1≤1 \leq n ≤3×104\leq 3 \times 10^4

  • 0≤0 \leq coins[i] ≤1\leq 1

  • edges.length == n - 1

  • edges[i].length == 2

  • 0≤0 \leq a_i, b_i << n

  • a_i != b_i

  • edges represents a valid tree.