2467. 树上最大得分和路径

来源第 91 场双周赛 Q3难度中等分数2053

题目描述

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

在每一个节点 i 处有一扇门。同时给你一个都是偶数的数组 amount ，其中 amount[i] 表示：

如果 amount[i] 的值是负数，那么它表示打开节点 i 处门扣除的分数。
如果 amount[i] 的值是正数，那么它表示打开节点 i 处门加上的分数。

游戏按照如下规则进行：

一开始，Alice 在节点 0 处，Bob 在节点 bob 处。
每一秒钟，Alice 和 Bob 分别移动到相邻的节点。Alice 朝着某个 叶子结点 移动，Bob 朝着节点 0 移动。
对于他们之间路径上的 每一个 节点，Alice 和 Bob 要么打开门并扣分，要么打开门并加分。注意：
- 如果门 已经打开 （被另一个人打开），不会有额外加分也不会扣分。
- 如果 Alice 和 Bob 同时到达一个节点，他们会共享这个节点的加分或者扣分。换言之，如果打开这扇门扣 c 分，那么 Alice 和 Bob 分别扣 c / 2 分。如果这扇门的加分为 c ，那么他们分别加 c / 2 分。
如果 Alice 到达了一个叶子结点，她会停止移动。类似的，如果 Bob 到达了节点 0 ，他也会停止移动。注意这些事件互相独立，不会影响另一方移动。

请你返回 Alice 朝最优叶子结点移动的最大净得分。

示例 1：

输入：edges = [[0,1],[1,2],[1,3],[3,4]], bob = 3, amount = [-2,4,2,-4,6]
输出：6
解释：
上图展示了输入给出的一棵树。游戏进行如下：
- Alice 一开始在节点 0 处，Bob 在节点 3 处。他们分别打开所在节点的门。
  Alice 得分为 -2 。
- Alice 和 Bob 都移动到节点 1 。
  因为他们同时到达这个节点，他们一起打开门并平分得分。
  Alice 的得分变为 -2 + (4 / 2) = 0 。
- Alice 移动到节点 3 。因为 Bob 已经打开了这扇门，Alice 得分不变。
  Bob 移动到节点 0 ，并停止移动。
- Alice 移动到节点 4 并打开这个节点的门，她得分变为 0 + 6 = 6 。
现在，Alice 和 Bob 都不能进行任何移动了，所以游戏结束。
Alice 无法得到更高分数。

示例 2：

输入：edges = [[0,1]], bob = 1, amount = [-7280,2350]
输出：-7280
解释：
Alice 按照路径 0->1 移动，同时 Bob 按照路径 1->0 移动。
所以 Alice 只打开节点 0 处的门，她的得分为 -7280 。

提示：

2 <= n <= 10⁵
edges.length == n - 1
edges[i].length == 2
0 <= a_i, b_i < n
a_i != b_i
edges 表示一棵有效的树。
1 <= bob < n
amount.length == n
amount[i] 是范围 [-10⁴, 10⁴] 之间的一个偶数。

解法

方法一：两次 DFS

思考

Bob 的路线固定为 \(bob\to 0\)，Alice 从 \(0\) 走向某一叶子。 \(n \le 10^5\)，先 DFS 记下 Bob 到达各点的时间 \(ts\)。

再从 \(0\) 出发 DFS：到达时刻等于 \(ts[i]\) 则平分收益，更早则独得，更晚则门已空。在叶子更新最大得分。

根据题意，我们可以知道，Bob 的移动路径是固定的，即从节点 \(bob\) 出发，最终到达节点 \(0\)。因此，我们可以先跑一遍 DFS，求出 Bob 到达每个节点的时间，记在数组 \(ts\) 中。

然后我们再跑一遍 DFS，求出 Alice 每条移动路径的最大得分，我们记 Alice 到达节点 \(i\) 的时间为 \(t\)，当前累计得分为 \(v\)，那么 Alice 在经过节点 \(i\) 处后，累计的分数有三种情况：

Alice 到达节点 \(i\) 的时间 \(t\) 与 Bob 到达节点 \(i\) 的时间 \(ts[i]\) 相同，那么 Alice 和 Bob 同时打开节点 \(i\) 处的门，Alice 获得的分数为 \(v + \frac{amount[i]}{2}\)；
Alice 到达节点 \(i\) 的时间 \(t\) 小于 Bob 到达节点 \(i\) 的时间 \(ts[i]\)，那么 Alice 打开节点 \(i\) 处的门，Alice 获得的分数为 \(v + amount[i]\)。
Alice 到达节点 \(i\) 的时间 \(t\) 大于 Bob 到达节点 \(i\) 的时间 \(ts[i]\)，那么 Alice 不打开节点 \(i\) 处的门，Alice 获得的分数为 \(v\)，即不变。

当 Alice 到达叶子节点时，更新最大得分。

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

Python3JavaC++Go

class Solution:
    def mostProfitablePath(
        self, edges: List[List[int]], bob: int, amount: List[int]
    ) -> int:
        def dfs1(i, fa, t):
            if i == 0:
                ts[i] = min(ts[i], t)
                return True
            for j in g[i]:
                if j != fa and dfs1(j, i, t + 1):
                    ts[j] = min(ts[j], t + 1)
                    return True
            return False

        def dfs2(i, fa, t, v):
            if t == ts[i]:
                v += amount[i] // 2
            elif t < ts[i]:
                v += amount[i]
            nonlocal ans
            if len(g[i]) == 1 and g[i][0] == fa:
                ans = max(ans, v)
                return
            for j in g[i]:
                if j != fa:
                    dfs2(j, i, t + 1, v)

        n = len(edges) + 1
        g = defaultdict(list)
        ts = [n] * n
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)
        dfs1(bob, -1, 0)
        ts[bob] = 0
        ans = -inf
        dfs2(0, -1, 0, 0)
        return ans

class Solution {
    private List<Integer>[] g;
    private int[] amount;
    private int[] ts;
    private int ans = Integer.MIN_VALUE;

    public int mostProfitablePath(int[][] edges, int bob, int[] amount) {
        int n = edges.length + 1;
        g = new List[n];
        ts = new int[n];
        this.amount = amount;
        Arrays.setAll(g, k -> new ArrayList<>());
        Arrays.fill(ts, n);
        for (var e : edges) {
            int a = e[0], b = e[1];
            g[a].add(b);
            g[b].add(a);
        }
        dfs1(bob, -1, 0);
        ts[bob] = 0;
        dfs2(0, -1, 0, 0);
        return ans;
    }

    private boolean dfs1(int i, int fa, int t) {
        if (i == 0) {
            ts[i] = Math.min(ts[i], t);
            return true;
        }
        for (int j : g[i]) {
            if (j != fa && dfs1(j, i, t + 1)) {
                ts[j] = Math.min(ts[j], t + 1);
                return true;
            }
        }
        return false;
    }

    private void dfs2(int i, int fa, int t, int v) {
        if (t == ts[i]) {
            v += amount[i] >> 1;
        } else if (t < ts[i]) {
            v += amount[i];
        }
        if (g[i].size() == 1 && g[i].get(0) == fa) {
            ans = Math.max(ans, v);
            return;
        }
        for (int j : g[i]) {
            if (j != fa) {
                dfs2(j, i, t + 1, v);
            }
        }
    }
}

class Solution {
public:
    int mostProfitablePath(vector<vector<int>>& edges, int bob, vector<int>& amount) {
        int n = edges.size() + 1;
        vector<vector<int>> g(n);
        for (auto& e : edges) {
            int a = e[0], b = e[1];
            g[a].emplace_back(b);
            g[b].emplace_back(a);
        }
        vector<int> ts(n, n);
        function<bool(int i, int fa, int t)> dfs1 = [&](int i, int fa, int t) -> bool {
            if (i == 0) {
                ts[i] = t;
                return true;
            }
            for (int j : g[i]) {
                if (j != fa && dfs1(j, i, t + 1)) {
                    ts[j] = min(ts[j], t + 1);
                    return true;
                }
            }
            return false;
        };
        dfs1(bob, -1, 0);
        ts[bob] = 0;
        int ans = INT_MIN;
        function<void(int i, int fa, int t, int v)> dfs2 = [&](int i, int fa, int t, int v) {
            if (t == ts[i])
                v += amount[i] >> 1;
            else if (t < ts[i])
                v += amount[i];
            if (g[i].size() == 1 && g[i][0] == fa) {
                ans = max(ans, v);
                return;
            }
            for (int j : g[i])
                if (j != fa) dfs2(j, i, t + 1, v);
        };
        dfs2(0, -1, 0, 0);
        return ans;
    }
};

func mostProfitablePath(edges [][]int, bob int, amount []int) int {
    n := len(edges) + 1
    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)
    }
    ts := make([]int, n)
    for i := range ts {
        ts[i] = n
    }
    var dfs1 func(int, int, int) bool
    dfs1 = func(i, fa, t int) bool {
        if i == 0 {
            ts[i] = min(ts[i], t)
            return true
        }
        for _, j := range g[i] {
            if j != fa && dfs1(j, i, t+1) {
                ts[j] = min(ts[j], t+1)
                return true
            }
        }
        return false
    }
    dfs1(bob, -1, 0)
    ts[bob] = 0
    ans := -0x3f3f3f3f
    var dfs2 func(int, int, int, int)
    dfs2 = func(i, fa, t, v int) {
        if t == ts[i] {
            v += amount[i] >> 1
        } else if t < ts[i] {
            v += amount[i]
        }
        if len(g[i]) == 1 && g[i][0] == fa {
            ans = max(ans, v)
            return
        }
        for _, j := range g[i] {
            if j != fa {
                dfs2(j, i, t+1, v)
            }
        }
    }
    dfs2(0, -1, 0, 0)
    return ans
}

方法二：两次显式栈

思考

Bob 的路线是树上从 \(bob\) 到根 \(0\) 的唯一路径，Alice 从 \(0\) 走向某个叶子，答案取她的最大净收入。\(n\le 10^5\)，沿一条链递归时调用深度等于节点数，链长达到 \(1000\) 就会超出 Python 的递归上限。路径唯一，不必在搜索中层层返回：先用栈从 \(0\) 记下父亲，再顺着父亲把 Bob 的到达时间写入 \(ts\)，其余节点保持哨兵 \(n\)。Alice 在节点 \(i\) 的得分只取决于她的时刻 \(t\) 与 \(ts[i]\) 的先后，第二遍用栈做前序。弹出时按同时、更早、更晚累加收益，仅当该点只与父亲相邻时才把它当作叶子并更新答案。

树上从 \(bob\) 到 \(0\) 只有一条路径。用显式栈从节点 \(0\) 遍历整棵树，记录每个节点的父亲。然后从 \(bob\) 沿着父亲走到 \(0\)，第 \(t\) 步到达的节点把 \(ts\) 设为 \(t\)。没有走到的节点保持初值 \(n\)，表示 Bob 不会经过。

接着用显式栈模拟 Alice 从 \(0\) 走向叶子。栈里存放节点、父亲、到达时刻 \(t\) 和进入该节点前的累计得分 \(v\)。弹出节点 \(i\) 后，累计得分有三种情况：

Alice 到达节点 \(i\) 的时间 \(t\) 与 Bob 到达节点 \(i\) 的时间 \(ts[i]\) 相同，那么 Alice 和 Bob 同时打开节点 \(i\) 处的门，Alice 获得的分数为 \(v + \frac{amount[i]}{2}\)；
Alice 到达节点 \(i\) 的时间 \(t\) 小于 Bob 到达节点 \(i\) 的时间 \(ts[i]\)，那么 Alice 打开节点 \(i\) 处的门，Alice 获得的分数为 \(v + amount[i]\)。
Alice 到达节点 \(i\) 的时间 \(t\) 大于 Bob 到达节点 \(i\) 的时间 \(ts[i]\)，那么 Alice 不打开节点 \(i\) 处的门，Alice 获得的分数为 \(v\)，即不变。

若 \(i\) 只有一个邻居且该邻居是父亲，则 \(i\) 是叶子，用当前得分更新答案。