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

题目

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

---

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

每个节点都有一个价值。给你一个整数数组 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^5
• edges.length == n - 1
• 0 <= ai, bi <= n - 1
• edges 表示一棵符合题面要求的树。
• price.length == n
• 1 <= price[i] <= 10^5

题解

方法一：

思路

求出每个节点u为根的子树最大路径和，以及不含叶子最大路径和。

在u为根的子树中经过节点u的最大路径和f[u] = u的子节点中最大的路径和+u的子节点中不含叶子的最大的路径和+1，这两条路径不能重叠。

整棵树的最大路径和肯定在某颗u为根的子树中且经过了u，对于所有u求出f[u]最大值即为整棵树的最大路径和。

如何保证求子节点两条路径不重叠？

在u为根的子树中

设x[i]u的第i个儿子的最大路径和

设y[i]u的第i个儿子的不含叶子最大路径和

设s1[i]是遍历u前i个儿子后，得到u子树最大路径和的最大值

设s2[i]是遍历u前i个儿子后，得到u子树不含叶子最大路径和的最大值

在没有儿子时，显然s1[0]=price[u], s2[0]=0。

在遍历第i个儿子时，可更新f[u]的情况：之前最大路径+当前不含叶子最大路径 或 之前不含叶子最大路径+当前最大路径，即s1[i]+x[i]或s2[i]+y[i]。

代码

class Solution {
public:
    using ll = long long;
    long long maxOutput(int n, vector<vector<int>>& edges, vector<int>& price) {
        vector<int> g[n];
        for (auto& i:edges) {
            g[i[0]].push_back(i[1]);
            g[i[1]].push_back(i[0]);
        }
        ll ans = 0;
        function<pair<ll,ll> (int,int)> dfs = [&](int u, int fa) -> pair<ll,ll> {
            ll p = price[u];
            ll s1 = price[u], s2 = 0;//无子树时，以u为根最大路径值，不含叶子最大路径值
            for (int i : g[u]) {
                if (i == fa) continue;
                auto [x, y] = dfs(i, u);
                ans = max(ans, max(s1+y, s2+x));
                //以遍历子树中，以u为根最大路径值，不含叶子最大路径值
                s1 = max(s1, x+p);
                s2 = max(s2, y+p);
            }
            return {s1, s2};
        };
        dfs(0, -1);
        return ans;
    }
};