Leetcode 2023-12-06 题目分享

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

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

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

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

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

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

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

示例 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 <= ai, bi <= n - 1
edges 表示一棵有效的树
price.length == n
price[i] 是一个偶数
1 <= price[i] <= 1000
1 <= trips.length <= 100
0 <= starti, endi <= n - 1

思路

首先肯定要根据访问的路径来统计每个节点最终会被访问多少次。
- 由于是一颗树，每次将起点当做根节点向下搜索即可。遇到终点就返回true，根据返回值来判断当前节点访问次数是否要++。
然后就是经典的01-DP问题：对于任何一个节点：
- 选择价格降低一半：那所有子节点都必须是原来价格
- 不选择：那那所有子节点可以减半，也可以不减半–取两者最小值

代码

class Solution {
public:
    int minimumTotalPrice(int n, vector<vector<int>>& edges, vector<int>& price, vector<vector<int>>& trips) {
        vector<int> g[n];
        for (vector<int>& e : edges){
            g[e[0]].push_back(e[1]);
            g[e[1]].push_back(e[0]);
        }
        vector<int> cnt(n);
        function<bool(int, int, int)> count = [&](int u, int fa, int end){
            if (u == end){
                cnt[u]++;
                return true;
            }
            for (int v : g[u]){
                if (v == fa) continue;
                if (count(v, u, end)){
                    cnt[u]++;
                    return true;
                }
            }
            return false;
        };
        for (vector<int>& t : trips) count(t[0], -1, t[1]);
        typedef pair<int, int> pii;
        function<pii(int, int)> dp = [&](int u, int fa){
            int select = price[u]/2*cnt[u], ignore = price[u]*cnt[u];
            for (int v : g[u]){
                if (v == fa) continue;
                pii cur = dp(v, u);
                select += cur.second;
                ignore += min(cur.first, cur.second);
            }
            return pair(select, ignore);
        };
        pii res = dp(0, -1);
        return min(res.first, res.second);
    }
};

复杂度分析

时间：O(n*t+n)=O(n*t)。n，t分别是节点数量和旅行次数。
空间：O(n)。