Uber – Optimize Delivery Network - Uber Online Assessment IIT BHU Data Science Role

Uber operates a delivery network consisting of N hubs connected by N − 1 bidirectional roads, forming a tree. Each road has a throughput value representing the number of deliveries it can efficiently support.

To reduce infrastructure costs, Uber plans to permanently close some roads. After the closures:

Each hub can remain directly connected to at most K other hubs. The remaining roads do not have to keep the network fully connected. The goal is to maximize the sum of throughput values of all roads that remain open.

Given the road network, determine the maximum total throughput that can be preserved.

Function Description

Complete the function maximizeDeliveryThroughput.

long long maximizeDeliveryThroughput(
    int n,
    vector<vector<int>> roads,
    int k
);

Parameters n — Number of hubs.

roads[i] = [u, v, w] — A bidirectional road connecting hubs u and v with throughput w.

k — Maximum number of roads that may remain connected to any hub.

Returns

long long — The maximum total throughput of the remaining roads.

Example 1:

Input:[5,[[0,1,4],[0,2,2],[2,3,12],[2,4,6]],2]

Output:22

Example 2:

Input:[7,[[0,1,5],[1,2,10],[0,3,15],[3,4,20],[3,5,5],[0,6,10]],3]

Output:65

Constraints:

2 ≤ n ≤ 100000

roads.size() = n - 1

1 ≤ w ≤ 10^6

1 ≤ k ≤ n - 1

The given graph is a tree.

solution.cpp

Run code to see test results

00:00 / 69:42