Minimize the Total Price of the Trips
01 · Problem
You are given an undirected tree with n nodes labelled 0 to n - 1, where edges[i] = [a_i, b_i] connects a_i and b_i. Each node has an even price price[i].
You also have a list of trips, where trips[i] = [start_i, end_i] means you travel from start_i to end_i along the unique path in the tree. The cost of a trip is the sum of the prices of every node on its path, including both endpoints (a trip with start_i == end_i costs just that node's price). If a node is visited by several trips, its price is paid once per trip.
Before any trip starts, you may pick a set of nodes, no two of which are adjacent, and halve the price of each picked node. The set may be empty. Return the minimum possible total cost of all the trips.
02 · Examples
n = 4, edges = [[0,1],[1,2],[1,3]], price = [2,2,10,6], trips = [[0,3],[2,1],[2,3]]
23
Halve nodes 0, 2 and 3 (no two of them are adjacent), so prices become [1,2,5,3]. Trip 0 -> 1 -> 3 costs 6, trip 2 -> 1 costs 7 and trip 2 -> 1 -> 3 costs 10, for a total of 23.
n = 2, edges = [[0,1]], price = [2,2], trips = [[0,0]]
1
Halve node 0. The only trip stays at node 0 and costs 1.
n = 3, edges = [[0,1],[1,2]], price = [4,8,6], trips = [[0,2]]
13
The trip visits all three nodes. Halving node 1 alone gives 4 + 4 + 6 = 14, while halving nodes 0 and 2 gives 2 + 8 + 3 = 13, which is the minimum.
03 · Constraints
- 011 <= n <= 50
- 02edges.length == n - 1 and the edges form a valid tree.
- 03price.length == n, and every price[i] is even with 2 <= price[i] <= 1000
- 041 <= trips.length <= 100
- 050 <= start_i, end_i < n
04 · Optimal complexity
- Time
- O(n * t)
- Space
- O(n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.