# 2646. Minimize the Total Price of the Trips
###### tags: `Leetcode` `Hard` `Dynamic Programming` `DFS`
Link: https://leetcode.com/problems/minimize-the-total-price-of-the-trips/description/
## 思路
首先遍历每一个trip 计算出如果不reduce任何一个price的total price 以及每个点都走了几次
接下来用dp计算最多能reduce多少price
这里计算的时候需要加memo 否则会超时
由于这个graph是一个tree 从任何一个点开始算dp都是一样的结果
## Code

class Solution {
    List<List<Integer>> graph;
    Map<Integer, Integer> freq;
    int[][] memo;
    public int minimumTotalPrice(int n, int[][] edges, int[] price, int[][] trips) {
        graph = new ArrayList<>();
        memo = new int[n][2];
        for(int i=0; i<n; i++){
            graph.add(new ArrayList<>());
            memo[i][0] = memo[i][1] = Integer.MAX_VALUE;
        }
        for(int[] edge:edges){
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }
        freq = new HashMap<>();
        int originalPrice = 0;
        for(int[] trip:trips){
            freq.put(trip[0], freq.getOrDefault(trip[0], 0)+1);
            originalPrice += price[trip[0]]+dfs(trip[0], -1, trip[1], price);
        }
        int reduce = Math.max(dp(0, -1, true, price), dp(0, -1, false, price));
        return originalPrice-reduce;
    }
    public int dfs(int start, int prev, int end, int[] price){
        if(start==end) return 0;
        for(int next:graph.get(start)){
            if(next==prev) continue;
            int nextPrice = dfs(next, start, end, price);
            if(nextPrice>=0){
                freq.put(next, freq.getOrDefault(next, 0)+1);
                return price[next]+nextPrice;
            }
        }
        return -1;
    }
    public int dp(int curr, int prev, boolean canReduce, int[] price){
        if(memo[curr][canReduce?0:1]!=Integer.MAX_VALUE) return memo[curr][canReduce?0:1];
        int reduce = 0, nextReduce = 0;
        if(canReduce) reduce += price[curr]/2*freq.getOrDefault(curr, 0);
        for(int next: graph.get(curr)){
            if(next==prev) continue;
            if(canReduce) nextReduce += dp(next, curr, false, price);
            else nextReduce += Math.max(dp(next, curr, true, price), dp(next, curr, false, price));
        }
        return memo[curr][canReduce?0:1] = reduce+nextReduce;
    }
}