Problem Brief

Uber Circular Shuttle Optimization

Uber has launched a new circular shuttle service that operates on a fixed route, starting and ending at the same location while collecting passengers from various designated stops.

The service area consists of n pickup locations, numbered from 0 to n-1. These locations are interconnected by roads, each with a uniform travel cost of 1 unit. The road network is defined by n-1 edges, where each edge [ai, bi] represents a bidirectional road connecting locations ai and bi. This configuration forms a connected tree structure of pickup locations.

Passenger demand is represented by an array of size n, where passengers[i] equals 1 if there's a passenger waiting at location i, and 0 otherwise.

The shuttle service operates as follows: The shuttle may begin its route at any pickup location. Two operations are available at each stop:

Passenger Collection (Cost: 0): Collect all passengers within a radius of 2 roads from the current location. The radius represents the maximum number of road segments the shuttle can reach to pick up passengers without additional cost.

Movement (Cost: 1): Travel to any directly connected pickup point, incurring a cost of 1 unit per road segment.

Objective: Determine the minimum total cost required to collect all waiting passengers and return the shuttle to its starting location.

Important Constraints:

Each time a road segment is traversed, it contributes 1 unit to the total cost (meaning a round trip on the same road costs 2 units).

The pickup locations form a valid tree structure (connected and acyclic).

Goal: Find the optimal starting location and route strategy that minimizes the total operational cost.

Note: If you pass a road 2 times, the cost to traverse that road becomes 2.

Function Description

Complete the function minimumShuttleCost in the editor.

minimumShuttleCost has the following parameters:

int[] passengers: A 1D array of integers where passengers[i] = 1 indicates a passenger at pickup point i, and passengers[i] = 0 indicates no passenger.
int[][] edges: A 2D array of integers where edges[i] = [ai, bi] indicates a bidirectional road connecting ai and bi.

Returns

int: Minimum cost incurred to start at a pickup point and return to the same starting point after collecting all the passengers from the pickup points.

1Example 1

Input

passengers = [1, 0, 0, 0, 0, 1], edges = [[0,1],[1,2],[2,3],[3,4],[4,5]]

Output

Explanation

The Uber shuttle can follow the below steps to reduce the cost to 2 and collect all 2 passengers: Start at pick-up point 2 Collect the passenger from pick-up point 0 Move to adjacent pick-up point 3 Collect the passenger from pick-up point 5 Move back to adjacent pick-up point 2 Cost is incurred only during movement from pick-up points 2 to 3 and 3 to 2. Total cost = 2.

2Example 2

Input

passengers = [0, 0, 0, 1, 1, 0, 0, 1], edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[5,6],[5,7]]

Output

Explanation

The Uber shuttle can follow the below steps to reduce the cost to 2 and collect all 3 passengers: Start at pick-up point 0 Collect the passengers from pick-up points 3 and 4 Move to adjacent pick-up point 2 Collect the passenger from pick-up point 7 Move back to adjacent pick-up point 0 Cost is incurred only during movement from pick-up points 0 to 2 and 2 to 0. Total cost = 2.

Constraints

Limits and guarantees your solution can rely on.

1 ≤ n ≤ 3·10^4
passengers.size() equals n.
0 ≤ passengers[i] ≤ 1
edges.length equals n-1.
edges[i].length equals 2.
0 ≤ ai, bi < n
ai ≠ bi