FastPrepFastPrep
Problem Brief

Collect Opportunity Data in a Tree

OA

You are given an undirected tree with n nodes labeled from 0 to n - 1. The tree is defined by n - 1 edges.

Each node represents a branch office. You are also given a binary array opportunityData of size n, where:

  • opportunityData[i] = 1 means branch i contains important data.
  • opportunityData[i] = 0 means it does not.

You may start at any node. You can traverse edges in both directions. You must start and end at the same node.

Special Rule:
When you are at a node, you can collect data from all nodes within distance <= 2 edges from your current location.

Return the minimum number of edges you must traverse to collect all important data.

1Example 1

Input
n = 11, edges = [[0,1],[0,2],[0,6],[1,3],[1,4],[3,10],[6,7],[7,8],[8,9]], opportunityData = [0,0,1,1,0,0,0,0,0,1,1]
Output
6
Explanation

Nodes 2, 3, 9, and 10 contain important data.

One optimal strategy:

  • Start at node 1.
  • From node 1, collect data at 3 and 10 (within distance 2).
  • Travel to node 0 and collect 2.
  • Travel toward node 7 to collect 9.
  • Return to the starting node.

Total edges traversed = 6.

Constraints

Limits and guarantees your solution can rely on.

  • 2 <= n <= 10^5
  • edges.length == n - 1
  • The input graph is a valid tree
  • opportunityData[i] is either 0 or 1
public int collectOpportunityDataInTree(int n, int[][] edges, int[] opportunityData) {
  // write your code here
}
Input

n

11

edges

[[0,1],[0,2],[0,6],[1,3],[1,4],[3,10],[6,7],[7,8],[8,9]]

opportunityData

[0,0,1,1,0,0,0,0,0,1,1]

Output

6

Sign in to submit your solution.