树上最大得分和路径

难度:

标签:

题目描述

一个 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⁴] 之间的一个偶数。

代码结果

运行时间: 222 ms, 内存: 54.9 MB

/*
 * 使用 Java Stream
 * 思路：
 * 1. 构建邻接表。
 * 2. 计算 Bob 的路径。
 * 3. 使用 Stream 计算最大得分路径。
 */

import java.util.*;
import java.util.stream.*;

public class SolutionStream {
    public int mostProfitablePath(int[][] edges, int bob, int[] amount) {
        int n = amount.length;
        List<Integer>[] graph = IntStream.range(0, n).mapToObj(i -> new ArrayList<Integer>()).toArray(List[]::new);
        Arrays.stream(edges).forEach(edge -> {
            graph[edge[0]].add(edge[1]);
            graph[edge[1]].add(edge[0]);
        });
        int[] bobPath = new int[n];
        Arrays.fill(bobPath, -1);
        findBobPath(graph, bob, 0, 0, bobPath);
        return dfs(graph, 0, -1, bobPath, amount, 0);
    }

    private boolean findBobPath(List<Integer>[] graph, int current, int target, int dist, int[] bobPath) {
        if (current == target) {
            bobPath[current] = dist;
            return true;
        }
        return graph[current].stream().anyMatch(neighbor -> bobPath[neighbor] == -1 && findBobPath(graph, neighbor, target, dist + 1, bobPath));
    }

    private int dfs(List<Integer>[] graph, int current, int parent, int[] bobPath, int[] amount, int time) {
        int score = time == bobPath[current] ? amount[current] / 2 : amount[current];
        return graph[current].stream().filter(neighbor -> neighbor != parent).mapToInt(neighbor -> dfs(graph, neighbor, current, bobPath, amount, time + 1)).max().orElse(0) + score;
    }
}

解释

方法:

这个题解采用了深度优先搜索（DFS）来解决问题。首先，对于Bob，我们从Bob所在的节点开始，使用DFS找到Bob到根节点0的路径，并记录Bob访问每个节点的时间。然后，我们再次从根节点0开始，使用DFS遍历树，同时记录Alice访问每个节点的时间。在这个过程中，我们比较Alice和Bob访问每个节点的时间，根据题目规则计算得分，并更新最大得分。当Alice到达一个叶子节点时，我们检查并更新最大得分。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆

为什么在`dfs_alice`函数中，当Alice和Bob同时到达一个节点时，分数只加了一半？这种处理方式在题目描述中有明确说明吗？

▷

在题解的代码中，当Alice和Bob同时到达一个节点时，节点的分数只加了一半，这是为了体现出这个节点同时被两人到达时的分配公平性。若两人同时到达一个节点，则他们共享该节点的分数，每人获得一半。这种处理是基于题目背景的合理假设，尽管这个细节在题目描述中可能没有明确说明，但根据常见的竞赛和实际问题处理逻辑，这种处理方式是合理的，可以避免重复计分的问题。

🦆

解决方案中提到在根节点添加了一个边界值`g[0].append(-1)`，这样做的目的是什么？如果没有这一步会发生什么？

▷

在根节点添加一个边界值`g[0].append(-1)`的目的是为了避免根节点被错误地判断为叶子节点。在`dfs_alice`函数中，通过检查一个节点的邻接列表长度是否为1来判断是否是叶子节点。如果不添加这个边界值，根节点在只有一个邻接节点时会被错误地判断为叶子节点，这会导致程序逻辑错误，因为根节点不应被视为叶子节点。这一步是为了确保遍历的正确性和逻辑的严谨性。

🦆

在`dfs_alice`函数中，对于每个节点的处理逻辑是如何确保Alice始终朝向叶子节点移动的？

▷

在`dfs_alice`函数中，Alice的移动是通过递归的深度优先搜索完成的。函数中通过遍历当前节点`x`的所有邻接节点`y`，并且只有当`y`不是父节点`fa`时才会递归地调用`dfs_alice`进入节点`y`。这样可以确保Alice从根节点出发，逐渐向下遍历树的每一个分支，直到到达叶子节点。通过这种方式，Alice可以探索所有可能的路径直到叶子节点，这保证了Alice始终朝向叶子节点移动。

🦆

在`dfs_bob`函数中，如果Bob所在的节点无法通过一条路径到达根节点0，这种情况在代码中是如何处理的？

▷

在`dfs_bob`函数中，如果Bob所在的节点无法通过一条路径到达根节点0，这种情况意味着从Bob的起点到根节点0不存在可达路径。在代码中，这通过递归函数的返回值来处理。如果从某节点`x`出发无法到达根节点，则递归调用`dfs_bob(y, x, t + 1)`将会返回`False`，并且不会更新`bob_time[x]`的值。因此，`bob_time[x]`将保持初始化的值，这意味着Bob从该节点到根节点的路径是不可达的。这样的处理可以在后续的比较中排除这些不可达的节点，确保程序的正确性。

树上最大得分和路径

题目描述

代码结果

解释

代码细节讲解

相关问题