Hard

题目描述

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

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

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

另外，给你一个二维整数数组 trips，其中 trips[i] = [starti, endi] 表示第 i 次旅行从节点 starti 开始，通过任意路径前往节点 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]。该路径的价格总和为 5 + 2 = 7。
对于第 3 次旅行，我们选择路径 [2,1,3]。该路径的价格总和为 5 + 2 + 3 = 10。
所有旅行的总价格为 6 + 7 + 10 = 23。

示例 2：

输入：n = 2, edges = [[0,1]], price = [2,2], trips = [[0,0]]
输出：1
解释：对于第 1 次旅行，我们选择路径 [0]。该路径的价格总和为 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

解题思路

这个问题需要分两步解决：

第一步：计算每个节点的访问频次 对于每次旅行，我们需要找到从起点到终点的路径，并统计每个节点在所有旅行中被访问的次数。由于是树结构，任意两点间只有唯一路径。我们可以使用DFS找到路径，并记录每个节点的访问频次。

第二步：树形动态规划选择减半节点 现在我们知道了每个节点的访问频次，问题转化为：在不相邻的节点中选择一些节点减半，使得总成本最小。这是一个经典的树形DP问题。

定义状态：

  • dp[v][0]：以v为根的子树中，v节点不减半时的最小成本
  • dp[v][1]：以v为根的子树中，v节点减半时的最小成本

状态转移：

  • dp[v][0] = price[v] * freq[v] + sum(min(dp[child][0], dp[child][1]))（v不减半，子节点可减半可不减半）
  • dp[v][1] = price[v]/2 * freq[v] + sum(dp[child][0])（v减半，所有子节点都不能减半）

最终答案是 min(dp[root][0], dp[root][1])，其中root可以是任意节点。

时间复杂度主要由寻找路径和树形DP两部分组成，都是O(n)级别的操作。

代码实现

class Solution {
public:
    vector<vector<int>> graph;
    vector<int> freq;
    vector<int> price;
    
    bool findPath(int curr, int target, int parent, vector<int>& path) {
        path.push_back(curr);
        if (curr == target) return true;
        
        for (int next : graph[curr]) {
            if (next != parent && findPath(next, target, curr, path)) {
                return true;
            }
        }
        path.pop_back();
        return false;
    }
    
    pair<int, int> dfs(int node, int parent) {
        int notHalve = price[node] * freq[node];
        int halve = price[node] / 2 * freq[node];
        
        for (int child : graph[node]) {
            if (child == parent) continue;
            auto [childNotHalve, childHalve] = dfs(child, node);
            notHalve += min(childNotHalve, childHalve);
            halve += childNotHalve;
        }
        
        return {notHalve, halve};
    }
    
    int minimumTotalPrice(int n, vector<vector<int>>& edges, vector<int>& price, vector<vector<int>>& trips) {
        this->price = price;
        graph.resize(n);
        freq.resize(n, 0);
        
        for (auto& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }
        
        for (auto& trip : trips) {
            vector<int> path;
            findPath(trip[0], trip[1], -1, path);
            for (int node : path) {
                freq[node]++;
            }
        }
        
        auto [notHalve, halve] = dfs(0, -1);
        return min(notHalve, halve);
    }
};

class Solution:
    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:
        graph = [[] for _ in range(n)]
        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)
        
        freq = [0] * n
        
        def find_path(curr, target, parent, path):
            path.append(curr)
            if curr == target:
                return True
            
            for next_node in graph[curr]:
                if next_node != parent and find_path(next_node, target, curr, path):
                    return True
            path.pop()
            return False
        
        for start, end in trips:
            path = []
            find_path(start, end, -1, path)
            for node in path:
                freq[node] += 1
        
        def dfs(node, parent):
            not_halve = price[node] * freq[node]
            halve = price[node] // 2 * freq[node]
            
            for child in graph[node]:
                if child == parent:
                    continue
                child_not_halve, child_halve = dfs(child, node)
                not_halve += min(child_not_halve, child_halve)
                halve += child_not_halve
            
            return not_halve, halve
        
        not_halve, halve = dfs(0, -1)
        return min(not_halve, halve)

public class Solution {
    private List<int>[] graph;
    private int[] freq;
    private int[] price;
    
    private bool FindPath(int curr, int target, int parent, List<int> path) {
        path.Add(curr);
        if (curr == target) return true;
        
        foreach (int next in graph[curr]) {
            if (next != parent && FindPath(next, target, curr, path)) {
                return true;
            }
        }
        path.RemoveAt(path.Count - 1);
        return false;
    }
    
    private (int, int) Dfs(int node, int parent) {
        int notHalve = price[node] * freq[node];
        int halve = price[node] / 2 * freq[node];
        
        foreach (int child in graph[node]) {
            if (child == parent) continue;
            var (childNotHalve, childHalve) = Dfs(child, node);
            notHalve += Math.Min(childNotHalve, childHalve);
            halve += childNotHalve;
        }
        
        return (notHalve, halve);
    }
    
    public int MinimumTotalPrice(int n, int[][] edges, int[] price, int[][] trips) {
        this.price = price;
        graph = new List<int>[n];
        freq = new int[n];
        
        for (int i = 0; i < n; i++) {
            graph[i] = new List<int>();
        }
        
        foreach (var edge in edges) {
            graph[edge[0]].Add(edge[1]);
            graph[edge[1]].Add(edge[0]);
        }
        
        foreach (var trip in trips) {
            var path = new List<int>();
            FindPath(trip[0], trip[1], -1, path);
            foreach (int node in path) {
                freq[node]++;
            }
        }
        
        var (notHalve, halve) = Dfs(0, -1);
        return Math.Min(notHalve, halve);
    }
}

var minimumTotalPrice = function(n, edges, price, trips) {
    // Build adjacency list
    const graph = Array(n).fill(null).map(() => []);
    for (const [a, b] of edges) {
        graph[a].push(b);
        graph[b].push(a);
    }
    
    // Count how many times each node is visited
    const count = Array(n).fill(0);
    
    // Find path between two nodes using DFS
    const findPath = (start, end, visited = new Set()) => {
        if (start === end) return [start];
        visited.add(start);
        
        for (const neighbor of graph[start]) {
            if (!visited.has(neighbor)) {
                const path = findPath(neighbor, end, visited);
                if (path) {
                    return [start, ...path];
                }
            }
        }
        return null;
    };
    
    // Count visits for each trip
    for (const [start, end] of trips) {
        const path = findPath(start, end);
        for (const node of path) {
            count[node]++;
        }
    }
    
    // Tree DP to find minimum cost
    const dfs = (node, parent) => {
        let noHalve = price[node] * count[node];
        let halve = (price[node] / 2) * count[node];
        
        for (const child of graph[node]) {
            if (child !== parent) {
                const [childNoHalve, childHalve] = dfs(child, node);
                noHalve += Math.min(childNoHalve, childHalve);
                halve += childNoHalve;
            }
        }
        
        return [noHalve, halve];
    };
    
    const [noHalve, halve] = dfs(0, -1);
    return Math.min(noHalve, halve);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n × trips.length + n) = O(n × trips.length)，其中寻找每次旅行路径需要O(n)，共有trips.length次；树形DP需要O(n)
空间复杂度O(n)，用于存储图的邻接表、频次数组和递归栈空间