2467. 树中最大收益路径

Medium

题目描述

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

在每个节点 i 处，都有一个门。还给你一个偶数整数数组 amount，其中 amount[i] 表示：

如果 amount[i] 为负数，表示打开节点 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

示例 2：

输入：edges = [[0,1]], bob = 1, amount = [-7280,2350]
输出：-7280

提示：

2 <= n <= 10^5
edges.length == n - 1
edges[i].length == 2
0 <= ai, bi < n
ai != bi
edges 表示一个有效的树
1 <= bob < n
amount.length == n
amount[i] 是范围 [-10^4, 10^4] 内的偶数

解题思路

这是一道树上路径问题，需要考虑 Alice 和 Bob 的移动策略。

核心思路：

Bob 的路径是固定的：Bob 从初始位置移动到节点 0，路径是确定的。我们需要先找到这条路径并记录 Bob 到达每个节点的时间。
Alice 的策略：Alice 要选择一条从节点 0 到某个叶节点的路径，使得净收入最大化。对于路径上的每个节点，需要考虑：
- 如果 Alice 先到达或独自到达：获得完整的 amount[i]
- 如果同时到达：获得 amount[i] / 2
- 如果 Bob 先到达：该节点已被访问，Alice 获得 0
算法步骤：
- 构建邻接表表示树
- 使用 DFS 找到 Bob 从起始位置到节点 0 的路径，记录每个节点被 Bob 访问的时间
- 使用 DFS 遍历所有可能的 Alice 路径（从节点 0 到叶节点），计算每条路径的净收入
- 在计算过程中，比较 Alice 和 Bob 到达同一节点的时间来决定收益分配
时间比较策略：
- 如果 Alice 到达时间 < Bob 到达时间：Alice 获得全部收益
- 如果 Alice 到达时间 = Bob 到达时间：平分收益
- 如果 Alice 到达时间 > Bob 到达时间：收益为 0（已被 Bob 获取）

通过遍历所有可能的叶节点路径，找到 Alice 能获得的最大净收入。

代码实现

class Solution {
public:
    int mostProfitablePath(vector<vector<int>>& edges, int bob, vector<int>& amount) {
        int n = amount.size();
        vector<vector<int>> graph(n);
        
        // 建图
        for (auto& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }
        
        // 找到Bob到根节点0的路径和时间
        vector<int> bobTime(n, -1);
        vector<bool> visited(n, false);
        
        function<bool(int, int)> findBobPath = [&](int node, int time) -> bool {
            if (node == 0) {
                bobTime[0] = time;
                return true;
            }
            
            visited[node] = true;
            for (int next : graph[node]) {
                if (!visited[next]) {
                    if (findBobPath(next, time + 1)) {
                        bobTime[node] = time;
                        return true;
                    }
                }
            }
            visited[node] = false;
            return false;
        };
        
        findBobPath(bob, 0);
        
        // Alice的DFS搜索最大收益
        int maxProfit = INT_MIN;
        visited.assign(n, false);
        
        function<void(int, int, int)> dfs = [&](int node, int time, int profit) {
            visited[node] = true;
            
            // 计算当前节点的收益
            int currentGain = 0;
            if (bobTime[node] == -1 || time < bobTime[node]) {
                // Alice先到达或Bob没有经过这个节点
                currentGain = amount[node];
            } else if (time == bobTime[node]) {
                // 同时到达，平分
                currentGain = amount[node] / 2;
            }
            // 如果Alice晚到达，收益为0
            
            profit += currentGain;
            
            // 检查是否为叶节点
            bool isLeaf = true;
            for (int next : graph[node]) {
                if (!visited[next]) {
                    isLeaf = false;
                    dfs(next, time + 1, profit);
                }
            }
            
            if (isLeaf) {
                maxProfit = max(maxProfit, profit);
            }
            
            visited[node] = false;
        };
        
        dfs(0, 0, 0);
        return maxProfit;
    }
};

class Solution:
    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:
        n = len(amount)
        graph = [[] for _ in range(n)]
        
        # 建图
        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)
        
        # 找到Bob到根节点0的路径和时间
        bob_time = [-1] * n
        visited = [False] * n
        
        def find_bob_path(node, time):
            if node == 0:
                bob_time[0] = time
                return True
            
            visited[node] = True
            for next_node in graph[node]:
                if not visited[next_node]:
                    if find_bob_path(next_node, time + 1):
                        bob_time[node] = time
                        return True
            visited[node] = False
            return False
        
        find_bob_path(bob, 0)
        
        # Alice的DFS搜索最大收益
        max_profit = float('-inf')
        visited = [False] * n
        
        def dfs(node, time, profit):
            nonlocal max_profit
            visited[node] = True
            
            # 计算当前节点的收益
            current_gain = 0
            if bob_time[node] == -1 or time < bob_time[node]:
                # Alice先到达或Bob没有经过这个节点
                current_gain = amount[node]
            elif time == bob_time[node]:
                # 同时到达，平分
                current_gain = amount[node] // 2
            # 如果Alice晚到达，收益为0
            
            profit += current_gain
            
            # 检查是否为叶节点
            is_leaf = True
            for next_node in graph[node]:
                if not visited[next_node]:
                    is_leaf = False
                    dfs(next_node, time + 1, profit)
            
            if is_leaf:
                max_profit = max(max_profit, profit)
            
            visited[node] = False
        
        dfs(0, 0, 0)
        return max_profit

public class Solution {
    public int MostProfitablePath(int[][] edges, int bob, int[] amount) {
        int n = amount.Length;
        List<int>[] graph = new List<int>[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new List<int>();
        }
        
        // 建图
        foreach (var edge in edges) {
            graph[edge[0]].Add(edge[1]);
            graph[edge[1]].Add(edge[0]);
        }
        
        // 找到Bob到根节点0的路径和时间
        int[] bobTime = new int[n];
        Array.Fill(bobTime, -1);
        bool[] visited = new bool[n];
        
        bool FindBobPath(int node, int time) {
            if (node == 0) {
                bobTime[0] = time;
                return true;
            }
            
            visited[node] = true;
            foreach (int next in graph[node]) {
                if (!visited[next]) {
                    if (FindBobPath(next, time + 1)) {
                        bobTime[node] = time;
                        return true;
                    }
                }
            }
            visited[node] = false;
            return false;
        }
        
        FindBobPath(bob, 0);
        
        // Alice的DFS搜索最大收益
        int maxProfit = int.MinValue;
        visited = new bool[n];
        
        void DFS(int node, int time, int profit) {
            visited[node] = true;
            
            // 计算当前节点的收益
            int currentGain = 0;
            if (bobTime[node] == -1 || time < bobTime[node]) {
                // Alice先到达或Bob没有经过这个节点
                currentGain = amount[node];
            } else if (time == bobTime[node]) {
                // 同时到达，平分
                currentGain = amount[node] / 2;
            }
            // 如果Alice晚到达，收益为0
            
            profit += currentGain;
            
            // 检查是否为叶节点
            bool isLeaf = true;
            foreach (int next in graph[node]) {
                if (!visited[next]) {
                    isLeaf = false;
                    DFS(next, time + 1, profit);
                }
            }
            
            if (isLeaf) {
                maxProfit = Math.Max(maxProfit, profit);
            }
            
            visited[node] = false;
        }
        
        DFS(0, 0, 0);
        return maxProfit;
    }
}

var mostProfitablePath = function(edges, bob, amount) {
    const n = amount.length;
    const graph = Array.from({length: n}, () => []);
    
    for (const [a, b] of edges) {
        graph[a].push(b);
        graph[b].push(a);
    }
    
    // Find Bob's path to node 0
    const bobPath = [];
    const bobVisited = new Set();
    
    function findBobPath(node, target, path) {
        if (node === target) {
            path.push(node);
            return true;
        }
        
        bobVisited.add(node);
        path.push(node);
        
        for (const neighbor of graph[node]) {
            if (!bobVisited.has(neighbor)) {
                if (findBobPath(neighbor, target, path)) {
                    return true;
                }
            }
        }
        
        path.pop();
        return false;
    }
    
    findBobPath(bob, 0, bobPath);
    
    // Create Bob's position at each time
    const bobAt = new Map();
    for (let i = 0; i < bobPath.length; i++) {
        bobAt.set(i, bobPath[i]);
    }
    
    // DFS for Alice to find maximum profit
    let maxProfit = -Infinity;
    
    function dfs(node, parent, time, profit) {
        let currentProfit = profit;
        
        // Check if Bob is at the same node at the same time
        if (bobAt.get(time) === node) {
            currentProfit += amount[node] / 2;
        } else if (!bobPath.includes(node) || bobPath.indexOf(node) > time) {
            // Alice gets full amount if Bob hasn't been here or will arrive later
            currentProfit += amount[node];
        }
        // If Bob was here earlier, Alice gets 0
        
        // Check if this is a leaf node
        const neighbors = graph[node].filter(neighbor => neighbor !== parent);
        if (neighbors.length === 0) {
            maxProfit = Math.max(maxProfit, currentProfit);
            return;
        }
        
        // Continue DFS to all neighbors
        for (const neighbor of neighbors) {
            dfs(neighbor, node, time + 1, currentProfit);
        }
    }
    
    dfs(0, -1, 0, 0);
    return maxProfit;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	分析
时间复杂度	O(n)
空间复杂度	O(n)

时间复杂度：O(n)，其中 n 是节点数量。找到 Bob 的路径需要

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目