Recently i encountered the following tree question in cisco online assessment.

A player has to collect coins from various locations. the city is represented as a tree with n vertices labelled from 0 to n-1. there is an array called coins of size n where coins[i] is either 0 or 1, 1 means coin present and vice versa.

The player must travel along the tree to collect all the coins. the distance between two vertices is the edge connecting the points and if the player is at x then he can only collect coins that are located within distance of 2 edges of that vertex x.

Player can choose any vertex to start but then must end at that starting vertex only. all edges are bidirectional.

We need to return the number of edges in the shortest path such that all coins are collected.

We need to complete the below function that take the following arguments:

int collectCoins(int treeNodes, vector<int> &coins,  vector<int> &tree_from,vector<int> &tree_to) {

} 

I was doing multisource bfs for this but was constantly getting wrong answer for the below test case:

treeNodes = 12
vector<int> coins = {1,0,1,1,0,0,1,0,1,0,0,1};
vector<int> tree_from = {0,1 ,2,3,4,5,6,8,3,9,10};
vector<int> tree_to   = {1,2,3,4,5,6,7,7,9,10,11};

expected output = 10;

i was able to solve a similar 1st question in the OA but wasn't able to do this due to complexity idk . please any help is appreciated. Thanks.