Leetcode #2646: Minimize the Total Price of the Trips
In this guide, we solve Leetcode #2646 Minimize the Total Price of the Trips in Python and focus on the core idea that makes the solution efficient.
You will see the intuition, the step-by-step method, and a clean Python implementation you can use in interviews.
Problem Statement
There exists an undirected and unrooted tree with n nodes indexed from 0 to n - 1. You are given the integer n and a 2D integer array edges of length n - 1, where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree.
Quick Facts
- Difficulty: Hard
- Premium: No
- Tags: Tree, Depth-First Search, Graph, Array, Dynamic Programming
Intuition
The problem breaks into overlapping subproblems, so caching results prevents exponential repetition.
A carefully chosen DP state captures exactly what we need to build the final answer.
Approach
Define the DP state and recurrence, then compute states in the correct order.
Optionally compress space once the recurrence is clear.
Steps:
- Choose a DP state definition.
- Write the recurrence and base cases.
- Compute states in the correct order.
Example
Input: n = 4, edges = [[0,1],[1,2],[1,3]], price = [2,2,10,6], trips = [[0,3],[2,1],[2,3]]
Output: 23
Explanation: The diagram above denotes the tree after rooting it at node 2. The first part shows the initial tree and the second part shows the tree after choosing nodes 0, 2, and 3, and making their price half.
For the 1st trip, we choose path [0,1,3]. The price sum of that path is 1 + 2 + 3 = 6.
For the 2nd trip, we choose path [2,1]. The price sum of that path is 2 + 5 = 7.
For the 3rd trip, we choose path [2,1,3]. The price sum of that path is 5 + 2 + 3 = 10.
The total price sum of all trips is 6 + 7 + 10 = 23.
It can be proven, that 23 is the minimum answer that we can achieve.
Python Solution
class Solution:
def minimumTotalPrice(
self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]
) -> int:
def dfs(i: int, fa: int, k: int) -> bool:
cnt[i] += 1
if i == k:
return True
ok = any(j != fa and dfs(j, i, k) for j in g[i])
if not ok:
cnt[i] -= 1
return ok
def dfs2(i: int, fa: int) -> (int, int):
a = cnt[i] * price[i]
b = a // 2
for j in g[i]:
if j != fa:
x, y = dfs2(j, i)
a += min(x, y)
b += x
return a, b
g = [[] for _ in range(n)]
for a, b in edges:
g[a].append(b)
g[b].append(a)
cnt = Counter()
for start, end in trips:
dfs(start, -1, end)
return min(dfs2(0, -1))
Complexity
The time complexity is , where and are the lengths of and respectively. The space complexity is .
Edge Cases and Pitfalls
Watch for boundary values, empty inputs, and duplicate values where applicable. If the problem involves ordering or constraints, confirm the invariant is preserved at every step.
Summary
This Python solution focuses on the essential structure of the problem and keeps the implementation interview-friendly while meeting the constraints.