Leetcode 2538. Difference Between Maximum and Minimum Price Sum

[Woodyiiiiiii]

这道题我一开始想用树状DP来做，但显然，我后来才明白，这不是正解，首先每个节点都是根节点，其次最重要的事没办法按顺序计算。

那只能用DFS了，但显然，单纯直接的DFS会是O(n^2)的时间复杂度。那怎么办呢？

其实这是个re-rooting问题， 利用缓存，将时间复杂度优化到O(2*n)。

思路：

1. 在遍历边的时候，用Map<Integer, List<long[]>>存储，key表示节点，val表示相邻节点和其最大值的集合
2. 然后遍历所有点，使用dfs(-1,root)深度dfs
3. dfs中，如果edge[1]为0，说明之前没有缓存，则继续深度遍历；否则直接用缓存
4. 最后，可以得到一个呈以某个点为中心，呈辐射状的DFS遍历+缓存。

class Solution {
    
    public long maxOutput(int n, int[][] edges, int[] price) {
        Map<Integer, List<long[]>> map = new HashMap<>();
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1];
            map.putIfAbsent(u, new ArrayList<>());
            map.putIfAbsent(v, new ArrayList<>());
            map.get(u).add(new long[]{v, 0});
            map.get(v).add(new long[]{u, 0});
        }

        long ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = Math.max(ans, dfs(i, -1, map, price) - price[i]);
        }
        return ans;
    }

    private long dfs(int u, int p, Map<Integer, List<long[]>> map, int[] price) {
        long max = price[u];
        if (!map.containsKey(u)) return max;
        for (long[] edge : map.get(u)) {
            int v = (int) edge[0];
            if (v == p) continue;
            if (edge[1] == 0) {
                edge[1] = dfs(v, u, map, price);
            }
            max = Math.max(max, edge[1] + price[u]);
        }
        return max;
    }

}

总结:
这种题型，我觉得叫DFS缓存。这类思路模版是：

1. 以0为根节点，进行预先DFS
2. 然后对于每个点，都保存一些数据，用map或者数组，相当于提前缓存了
3. 最后再从0(或者所有点)开始DFS，利用好这些数据，找到移动规律，使时间复杂度为O(k*n)，k为常数

难点在于要想到要存什么数据，和找到移动的关系。

类似题目:

• 834. Sum of Distances in Tree
• 124. Binary Tree Maximum Path Sum
• 2458. Height of Binary Tree After Subtree Removal Queries (未完成)

下面链接中的讲解，可以仔细看看。

---

• 2538. Difference Between Maximum and Minimum Price Sum
• https://leetcode.com/problems/difference-between-maximum-and-minimum-price-sum/solutions/3052569/template-for-tree-based-dp-problems-with-edges-inputs/
• https://leetcode.com/problems/difference-between-maximum-and-minimum-price-sum/solutions/3052596/re-rooting/
• https://leetcode.com/problems/difference-between-maximum-and-minimum-price-sum/solutions/3052985/c-dfs-beats-100/
• https://leetcode.cn/problems/difference-between-maximum-and-minimum-price-sum/solutions/2062783/huan-gen-dong-tai-gui-hua-jie-fa-by-vcli-gaii/

---

第二种方法：同样是两遍DFS。做法：https://leetcode.com/problems/difference-between-maximum-and-minimum-price-sum/solutions/3052596/Re-rooting-or-O(N)-or-Explained/?orderBy=hot

记录根节点和他的最大子路径和第二大子路径。

更多re-rooting问题：2581. Count Number of Possible Root Nodes