LC 2646. 最小化旅行的价格总和

题目描述

这是 LeetCode 上的 2646. 最小化旅行的价格总和 ，难度为 困难。

现有一棵无向、无根的树，树中有 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：

1
2
3
4
5
6
7
8
9
10
输入：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：

1
2
3
4
5
6
7
8
输入：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$

DFS

Java 代码：

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
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
    int N = 55, M = N * 2, idx = 0;
    int[] he = new int[N], e = new int[M], ne = new int[M];
    void add(int a, int b) {
        e[idx] = b;
        ne[idx] = he[a];
        he[a] = idx++;
    }
    public int minimumTotalPrice(int n, int[][] edges, int[] price, int[][] trips) {
        Arrays.fill(he, -1);
        for (int[] info : edges) {
            add(info[0], info[1]); add(info[1], info[0]);
        }
        int[] cnt = new int[n];
        for (int[] trip : trips) dfs1(trip[0], -1, trip[1], cnt);
        int[] ans = dfs2(0, -1, price, cnt);
        return Math.min(ans[0], ans[1]);
    }
    int[] dfs2(int u, int fa, int[] price, int[] cnt) {
        int a = price[u] / 2 * cnt[u], b = price[u] * cnt[u];
        for (int i = he[u]; i != -1; i = ne[i]) {
            int j = e[i];
            if (j == fa) continue;
            int[] info = dfs2(j, u, price, cnt);
            int c = info[0], d = info[1];
            a += d; b += Math.min(c, d);
        }
        return new int[]{a, b};
    }
    boolean dfs1(int u, int fa, int end, int[] cnt) {
        if (u == end) {
            cnt[u]++;
            return true;
        }
        for (int i = he[u]; i != -1; i = ne[i]) {
            int j = e[i];
            if (j == fa) continue;
            if (dfs1(j, u, end, cnt)) {
                cnt[u]++;
                return true;
            }
        }
        return false;
    }
}

C++ 代码：

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
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
public:
    int he[55], e[55 * 2], ne[55 * 2], idx = 0;
    void add(int a, int b) {
        e[idx] = b;
        ne[idx] = he[a];
        he[a] = idx++;
    }
    int minimumTotalPrice(int n, vector<vector<int>>& edges, vector<int>& price, vector<vector<int>>& trips) {
        memset(he, -1, sizeof(he));
        for (auto& info : edges) {
            add(info[0], info[1]); add(info[1], info[0]);
        }
        vector<int> cnt(n, 0);
        for (auto& trip : trips) dfs1(trip[0], -1, trip[1], cnt);
        vector<int> ans = dfs2(0, -1, price, cnt);
        return min(ans[0], ans[1]);
    }
    vector<int> dfs2(int u, int fa, vector<int>& price, vector<int>& cnt) {
        int a = price[u] / 2 * cnt[u], b = price[u] * cnt[u];
        for (int i = he[u]; i != -1; i = ne[i]) {
            int j = e[i];
            if (j == fa) continue;
            vector<int> info = dfs2(j, u, price, cnt);
            int c = info[0], d = info[1];
            a += d; b += min(c, d);
        }
        return {a, b};
    }
    bool dfs1(int u, int fa, int end, vector<int>& cnt) {
        if (u == end) {
            cnt[u]++;
            return true;
        }
        for (int i = he[u]; i != -1; i = ne[i]) {
            int j = e[i];
            if (j == fa) continue;
            if (dfs1(j, u, end, cnt)) {
                cnt[u]++;
                return true;
            }
        }
        return false;
    }
};

Python 代码：
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
33
34
35
36
37
38
39
40
41
42
class Solution:    
    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:
        idx = 0
        he, e, ne = [-1] * n, [0] * n * 2, [0] * n * 2

        def add(a, b):
            nonlocal idx
            e[idx], ne[idx], he[a] = b, he[a], idx
            idx += 1
    
        def dfs1(u, fa, end):
            if u == end:
                cnt[u] += 1
                return True
            i = he[u]
            while i != -1:
                j, i = e[i], ne[i]
                if j == fa: continue
                if dfs1(j, u, end):
                    cnt[u] += 1
                    return True
            return False
        
        def dfs2(u, fa):
            a, b = price[u] // 2 * cnt[u], price[u] * cnt[u]
            i = he[u]
            while i != -1:
                j, i = e[i], ne[i]
                if j == fa: continue
                c, d = dfs2(j, u)
                a += d
                b += min(c, d)
            return [a, b]

        for info in edges:
            add(info[0], info[1])
            add(info[1], info[0])
        cnt = [0] * n
        for trip in trips:
            dfs1(trip[0], -1, trip[1])
        ans = dfs2(0, -1)
        return min(ans[0], ans[1])

TypeScript 代码：
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
33
34
35
36
37
38
39
40
41
function minimumTotalPrice(n: number, edges: number[][], price: number[], trips: number[][]): number {
    let N = n + 10, M = N * 2, idx = 0;
    const he = Array(N).fill(-1), e = Array(N).fill(0), ne = Array(N).fill(0);
    const add = function(a: number, b: number): void {
        e[idx] = b;
        ne[idx] = he[a];
        he[a] = idx++;
    };
    const dfs1 = function(u: number, fa: number, end: number): boolean {
        if (u == end) {
            cnt[u]++;
            return true;
        }
        for (let i = he[u]; i != -1; i = ne[i]) {
            const j = e[i];
            if (j == fa) continue;
            if (dfs1(j, u, end)) {
                cnt[u]++;
                return true;
            }
        }
        return false;
    };
    const dfs2 = function(u: number, fa: number): number[] {
        let a = price[u] / 2 * cnt[u], b = price[u] * cnt[u];
        for (let i = he[u]; i != -1; i = ne[i]) {
            const j = e[i];
            if (j == fa) continue;
            const [c, d] = dfs2(j, u);
            a += d; b += Math.min(c, d);
        }
        return [a, b];
    }
    for (const [a, b] of edges) {
        add(a, b); add(b, a);
    }
    const cnt = Array(N).fill(0)
    for (const [a, b] of trips) dfs1(a, -1, b);
    const [a, b] = dfs2(0, -1);
    return Math.min(a, b);
};

  • 时间复杂度：令 m 为 trips 的大小，建图复杂度为 $O(n)$；统计完成 trips 时，每个点的经过次数 cnt 的复杂度为 $O(m \times n)$；最后统计答案复杂度为 $O(n)$。整体复杂度为 $O(m \times n)$
  • 空间复杂度：$O(n)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.2646 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。