Maximum Cities Visitable from City 0 | Dataford Interview Questions

In a tree of n cities with an entry cost per city and m dollars, starting from city 0, find the maximum number of cities you can visit

Represent the tree with n and an edge list. Visiting a city pays its entry cost once, and every visited city must be reachable from city 0 through visited cities. Return the maximum number of visited cities, or 0 if city 0 cannot be entered.

Input and Output

max_cities(n, edges, entry_cost, m) returns an integer.

Constraints

1 <= n <= 200
edges contains exactly n - 1 undirected edges and forms a tree
0 <= m <= 10^9
1 <= entry_cost[i] <= 10^6
City 0 is the required starting city

Function Signature

def max_cities(n, edges, entry_cost, m):

Your question is Maximum Cities Visitable from City 0. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem