2538. 最大价值和与最小价值和的差值

来源第 328 场周赛 Q4难度困难分数2397

题目描述

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

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

一条路径的 价值和 是这条路径上所有节点的价值之和。

你可以选择树中任意一个节点作为根节点 root 。选择 root 为根的开销是以 root 为起点的所有路径中，价值和 最大的一条路径与最小的一条路径的差值。

请你返回所有节点作为根节点的选择中，最大的开销为多少。

示例 1：

输入：n = 6, edges = [[0,1],[1,2],[1,3],[3,4],[3,5]], price = [9,8,7,6,10,5]
输出：24
解释：上图展示了以节点 2 为根的树。左图（红色的节点）是最大价值和路径，右图（蓝色的节点）是最小价值和路径。
- 第一条路径节点为 [2,1,3,4]：价值为 [7,8,6,10] ，价值和为 31 。
- 第二条路径节点为 [2] ，价值为 [7] 。
最大路径和与最小路径和的差值为 24 。24 是所有方案中的最大开销。

示例 2：

输入：n = 3, edges = [[0,1],[1,2]], price = [1,1,1]
输出：2
解释：上图展示了以节点 0 为根的树。左图（红色的节点）是最大价值和路径，右图（蓝色的节点）是最小价值和路径。
- 第一条路径包含节点 [0,1,2]：价值为 [1,1,1] ，价值和为 3 。
- 第二条路径节点为 [0] ，价值为 [1] 。
最大路径和与最小路径和的差值为 2 。2 是所有方案中的最大开销。

提示：

1 <= n <= 10⁵
edges.length == n - 1
0 <= a_i, b_i <= n - 1
edges 表示一棵符合题面要求的树。
price.length == n
1 <= price[i] <= 10⁵

解法

方法一：树形 DP

思考

树上一条路径的代价是点权和减去两个端点中的较小者，求所有路径的最大代价。价格均为正，较小端点总是路径上较矮的一端，等价于“整条路径和减去一个端点”。枚举所有路径需 \(O(n^2)\)。

树形 DP 对每个子树维护两条量：从根出发不删端点的最长链 \(a\)，以及删去远端端点的最长链 \(b\)。跨过当前结点时，一侧取 \(a\) 另一侧取对方的 \(d\)（已删端点），或一侧取 \(b\) 另一侧取对方的 \(c\)，即可拼出经过该结点的最优路径。

由于每个节点价值均为正整数，因此，以节点 \(\textit{root}\) 作为根节点的最小的一条路径就是 \(\textit{root}\) 节点本身，那么价值和最大的一条路径与最小的一条路径的差值就等价于去掉路径的一个端点。

我们设计一个函数 \(\textit{dfs}(i, fa)\)，表示以节点 \(i\) 为根节点的子树中，不去掉端点的最大路径和以及去掉端点的最大路径和。其中， \(fa\) 表示节点 \(i\) 的父节点。

函数 \(\textit{dfs}(i, fa)\) 的实现逻辑如下：

初始化 \(a = \textit{price}[i]\), \(b = 0\)，表示初始只有一个节点，不去掉端点的最大路径和为 \(\textit{price}[i]\)，去掉端点的最大路径和为 \(0\)。

对于节点 \(i\) 的每个子节点 \(j\)，如果 \(j \ne fa\)，则递归调用函数 \(\textit{dfs}(j, i)\)，这里返回了以节点 \(j\) 为根节点的子树中，不去掉端点的最大路径和以及去掉端点的最大路径和，记为 \(c\) 和 \(d\)。此时答案有两种情况：

前面不去掉端点的最大路径和加上当前节点去掉端点的最大路径和，即 \(a + d\)；
前面去掉端点的最大路径和加上当前节点不去掉端点的最大路径和，即 \(b + c\)。

我们更新答案的最大值，即 \(\textit{ans} = \max(\textit{ans}, a + d, b + c)\)。

然后更新 \(a\) 和 \(b\)，即 \(a = \max(a, \textit{price}[i] + c)\), \(b = \max(b, \textit{price}[i] + d)\)，最后返回。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 为节点个数。

Python3JavaC++Go

class Solution:
    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:
        def dfs(i, fa):
            a, b = price[i], 0
            for j in g[i]:
                if j != fa:
                    c, d = dfs(j, i)
                    nonlocal ans
                    ans = max(ans, a + d, b + c)
                    a = max(a, price[i] + c)
                    b = max(b, price[i] + d)
            return a, b

        g = defaultdict(list)
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)
        ans = 0
        dfs(0, -1)
        return ans

class Solution {
    private List<Integer>[] g;
    private long ans;
    private int[] price;

    public long maxOutput(int n, int[][] edges, int[] price) {
        g = new List[n];
        Arrays.setAll(g, k -> new ArrayList<>());
        for (var e : edges) {
            int a = e[0], b = e[1];
            g[a].add(b);
            g[b].add(a);
        }
        this.price = price;
        dfs(0, -1);
        return ans;
    }

    private long[] dfs(int i, int fa) {
        long a = price[i], b = 0;
        for (int j : g[i]) {
            if (j != fa) {
                var e = dfs(j, i);
                long c = e[0], d = e[1];
                ans = Math.max(ans, Math.max(a + d, b + c));
                a = Math.max(a, price[i] + c);
                b = Math.max(b, price[i] + d);
            }
        }
        return new long[] {a, b};
    }
}

class Solution {
public:
    long long maxOutput(int n, vector<vector<int>>& edges, vector<int>& price) {
        vector<vector<int>> g(n);
        for (auto& e : edges) {
            int a = e[0], b = e[1];
            g[a].push_back(b);
            g[b].push_back(a);
        }
        using ll = long long;
        using pll = pair<ll, ll>;
        ll ans = 0;
        function<pll(int, int)> dfs = [&](int i, int fa) {
            ll a = price[i], b = 0;
            for (int j : g[i]) {
                if (j != fa) {
                    auto [c, d] = dfs(j, i);
                    ans = max({ans, a + d, b + c});
                    a = max(a, price[i] + c);
                    b = max(b, price[i] + d);
                }
            }
            return pll{a, b};
        };
        dfs(0, -1);
        return ans;
    }
};

func maxOutput(n int, edges [][]int, price []int) int64 {
    g := make([][]int, n)
    for _, e := range edges {
        a, b := e[0], e[1]
        g[a] = append(g[a], b)
        g[b] = append(g[b], a)
    }
    type pair struct{ a, b int }
    ans := 0
    var dfs func(i, fa int) pair
    dfs = func(i, fa int) pair {
        a, b := price[i], 0
        for _, j := range g[i] {
            if j != fa {
                e := dfs(j, i)
                c, d := e.a, e.b
                ans = max(ans, max(a+d, b+c))
                a = max(a, price[i]+c)
                b = max(b, price[i]+d)
            }
        }
        return pair{a, b}
    }
    dfs(0, -1)
    return int64(ans)
}

方法二：树形 DP + 显式栈

思考

树上一条路径的代价是点权和减去两个端点中的较小者。价格均为正，这等价于整条路径和减去一个端点。 \(n \le 10^5\)，枚举路径是 \(O(n^2)\)；从根递归维护每棵子树的两条向下链，链上的调用深度就是 \(n\)，会超出递归栈。

每个节点需要两条量：不删远端端点的最长向下链 \(a\)，以及删去远端端点的最长向下链 \(b\)。经过当前点的最优路径，是把已经得到的一条链与某个孩子的另一条链接上， \(a\) 配孩子的 \(d\)，或 \(b\) 配孩子的 \(c\)。

显式栈按 \((节点, 父节点, 状态)\) 做后序。进入时先压出栈标记再压孩子，离开时用孩子已经写下的两条链更新答案，并留下本节点的 \(a\) 和 \(b\)。

由于每个节点价值均为正整数，因此，以节点 \(\textit{root}\) 作为根节点的最小的一条路径就是 \(\textit{root}\) 节点本身，那么价值和最大的一条路径与最小的一条路径的差值就等价于去掉路径的一个端点。

对每个节点 \(i\) 维护两个量：不去掉端点的最大向下路径和 \(a\)，以及去掉远端端点的最大向下路径和 \(b\)。用显式栈从根做后序，离开节点时再计算这两个量。

初始化 \(a = \textit{price}[i]\)， \(b = 0\)，表示只有节点 \(i\) 自己。

对于每个子节点 \(j\)，它的两个量已经记为 \(c\) 和 \(d\)。经过 \(i\) 的路径有两种拼法：

前面不去掉端点的最大路径和加上当前子树去掉端点的最大路径和，即 \(a + d\)；
前面去掉端点的最大路径和加上当前子树不去掉端点的最大路径和，即 \(b + c\)。