What is the main algorithmic pattern for Minimize the Total Price of the Trips?

The core pattern is graph traversal with depth-first search combined with dynamic programming on trees to minimize repeated node contributions.

How do I calculate the frequency of node visits across all trips?

Use DFS for each trip to trace the path from start to end, incrementing a frequency counter for every node encountered.

Can nodes be halved more than once?

No, each node price can only be halved once. The DP ensures the best subset of nodes is selected to minimize the total cost.

What are common mistakes when solving this problem?

Common mistakes include ignoring multiple visits of nodes across trips, miscalculating DP states, and using brute-force path enumeration.

Is this problem solvable without dynamic programming?

Not efficiently; without DP, choosing which nodes to halve may require exponential checks over subsets, making it infeasible even for n = 50.

#2646

Hard

auto_awesome图·DFS·traversal

LeetCode 题解工作台

最小化旅行的价格总和

现有一棵无向、无根的树，树中有 n 个节点，按从 0 到 n - 1 编号。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [a i , b i ] 表示树中节点 a i 和 b i 之间存在一条边。每个节点都关联一个价格。给你一个整数数组 p…

数组动态规划树深度优先搜索图

题目描述

现有一棵无向、无根的树，树中有 n 个节点，按从 0 到 n - 1 编号。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [a_i, b_i] 表示树中节点 a_i 和 b_i 之间存在一条边。

每个节点都关联一个价格。给你一个整数数组 price ，其中 price[i] 是第 i 个节点的价格。

给定路径的 价格总和 是该路径上所有节点的价格之和。

另给你一个二维整数数组 trips ，其中 trips[i] = [start_i, end_i] 表示您从节点 start_i 开始第 i 次旅行，并通过任何你喜欢的路径前往节点 end_i 。

在执行第一次旅行之前，你可以选择一些 非相邻节点 并将价格减半。

返回执行所有旅行的最小价格总和。

示例 1：

输入：n = 4, edges = [[0,1],[1,2],[1,3]], price = [2,2,10,6], trips = [[0,3],[2,1],[2,3]]
输出：23
解释：
上图表示将节点 2 视为根之后的树结构。第一个图表示初始树，第二个图表示选择节点 0 、2 和 3 并使其价格减半后的树。
第 1 次旅行，选择路径 [0,1,3] 。路径的价格总和为 1 + 2 + 3 = 6 。
第 2 次旅行，选择路径 [2,1] 。路径的价格总和为 2 + 5 = 7 。
第 3 次旅行，选择路径 [2,1,3] 。路径的价格总和为 5 + 2 + 3 = 10 。
所有旅行的价格总和为 6 + 7 + 10 = 23 。可以证明，23 是可以实现的最小答案。

示例 2：

输入：n = 2, edges = [[0,1]], price = [2,2], trips = [[0,0]]
输出：1
解释：
上图表示将节点 0 视为根之后的树结构。第一个图表示初始树，第二个图表示选择节点 0 并使其价格减半后的树。 
第 1 次旅行，选择路径 [0] 。路径的价格总和为 1 。 
所有旅行的价格总和为 1 。可以证明，1 是可以实现的最小答案。

提示：

1 <= n <= 50
edges.length == n - 1
0 <= a_i, b_i <= n - 1
edges 表示一棵有效的树
price.length == n
price[i] 是一个偶数
1 <= price[i] <= 1000
1 <= trips.length <= 100
0 <= start_i, end_i <= n - 1

lightbulb

解题思路

方法一：树形 DP

我们可以统计每一次旅行经过的节点，记录在数组 $cnt$ 中，其中 $cnt[i]$ 表示所有旅行中经过节点 $i$ 的次数。我们设计一个函数 $dfs(i, fa, k)$ ，表示从节点 $i$ 开始搜索，最终到达节点 $k$ ，过程中记录所有经过的节点。其中 $fa$ 表示节点 $i$ 的父节点。

接下来，我们再设计一个函数 $dfs2(i, fa)$ ，表示从节点 $i$ 开始搜索，返回将节点 $i$ 的价格不减半或者减半后的最小价格总和。其中 $fa$ 表示节点 $i$ 的父节点。

我们从节点 $0$ 开始，对于每一个节点 $i$ ，我们可以选择不将其价格减半，也可以选择将其价格减半，分别记为 $a = cnt[i] \times price[i]$ , $b = \frac{a}{2}$ 。

对于节点 $i$ 的所有邻接节点 $j$ ，我们依然可以选择不将其价格减半，也可以选择将其价格减半，那么 $(x, y) = dfs2(j, i)$ 。如果节点 $i$ 价格不减半，那么节点 $j$ 价格可以不减半，也可以减半，因此 $a = a + \min(x, y)$ ；如果节点 $i$ 价格减半，那么节点 $j$ 价格必须不减半，因此 $b = b + x$ 。

最后，函数 $dfs2(i, fa)$ 的返回值为 $(a, b)$ 。

在主函数中，我们调用函数 $dfs2(0, -1)$ ，返回值为 $(a, b)$ ，那么最终的答案即为 $\min(a, b)$ 。

时间复杂度 $O(m \times n)$ ，空间复杂度 $O(n)$ 。其中 $m$ 和 $n$ 分别为旅行次数以及节点数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

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))

speed

复杂度分析

指标	值
时间	complexity is O(n * trips) for computing DFS paths plus O(n) for the DP traversal. Space complexity is O(n) for frequency array and DP states, keeping memory usage linear relative to the number of nodes.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check if the candidate identifies DFS as the tool for counting node frequencies.
question_mark
Listen for correct formulation of two DP states per node to consider halving or not.
question_mark
Observe if they optimize repeated trip paths using memoization or frequency accumulation.

warning

常见陷阱

外企场景

error
Forgetting to count multiple visits of a node across different trips, underestimating its contribution.
error
Incorrectly combining DP states, leading to non-optimal halving choices.
error
Attempting brute-force path enumeration without DFS, resulting in timeouts even for small n.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Instead of halving node prices, consider reducing each node price by a fixed amount and compute minimum total cost.
arrow_right_alt
Allow edges to have weights and optimize trips cost including edge weights along with node prices.
arrow_right_alt
Limit the number of nodes that can be halved and find the minimal achievable total trip cost.

help

常见问题

外企场景

继续练习

#2581 统计可能的树根数目 #2467 树上最大得分和路径 #2368 受限条件下可到达节点的数目