跳至主要內容

2467. 树上最大得分和路径

2467. 树上最大得分和路径

🟠   🔖  树 深度优先搜索 广度优先搜索 图 数组  🔗 力扣open in new window LeetCodeopen in new window

题目

There is an undirected tree with n nodes labeled from 0 to n - 1, rooted at node 0. You are given a 2D integer array edges of length n - 1 where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree.

At every node i, there is a gate. You are also given an array of even integers amount, where amount[i] represents:

  • the price needed to open the gate at node i, if amount[i] is negative, or,
  • the cash reward obtained on opening the gate at node i, otherwise.

The game goes on as follows:

  • Initially, Alice is at node 0 and Bob is at node bob.

  • At every second, Alice and Bob each move to an adjacent node. Alice moves towards some leaf node , while Bob moves towards node 0.

  • For every node along their path, Alice and Bob either spend money to open the gate at that node, or accept the reward. Note that:

    • If the gate is already open , no price will be required, nor will there be any cash reward.

    • If Alice and Bob reach the node simultaneously , they share the price/reward for opening the gate there. In other words, if the price to open the gate is c, then both Alice and Bob pay c / 2 each. Similarly, if the reward at the gate is c, both of them receive c / 2 each.

  • If Alice reaches a leaf node, she stops moving. Similarly, if Bob reaches node 0, he stops moving. Note that these events are independent of each other.

Return the maximum net income Alice can have if she travels towards the optimal leaf node.

Example 1:

Input: edges = [[0,1],[1,2],[1,3],[3,4]], bob = 3, amount = [-2,4,2,-4,6]

Output: 6

Explanation:

The above diagram represents the given tree. The game goes as follows:

  • Alice is initially on node 0, Bob on node 3. They open the gates of their respective nodes.

    Alice's net income is now -2.

  • Both Alice and Bob move to node 1.

    Since they reach here simultaneously, they open the gate together and share the reward.

    Alice's net income becomes -2 + (4 / 2) = 0.

  • Alice moves on to node 3. Since Bob already opened its gate, Alice's income remains unchanged.

    Bob moves on to node 0, and stops moving.

  • Alice moves on to node 4 and opens the gate there. Her net income becomes 0 + 6 = 6.

Now, neither Alice nor Bob can make any further moves, and the game ends.

It is not possible for Alice to get a higher net income.

Example 2:

Input: edges = [[0,1]], bob = 1, amount = [-7280,2350]

Output: -7280

Explanation:

Alice follows the path 0->1 whereas Bob follows the path 1->0.

Thus, Alice opens the gate at node 0 only. Hence, her net income is -7280.

Constraints:

  • 2 <= n <= 10^5
  • edges.length == n - 1
  • edges[i].length == 2
  • 0 <= ai, bi < n
  • ai != bi
  • edges represents a valid tree.
  • 1 <= bob < n
  • amount.length == n
  • amount[i] is an even integer in the range [-10^4, 10^4].

题目大意

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

在每一个节点 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^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] 之间的一个 偶数 。

解题思路

  1. 建图：由于输入是一棵树，我们使用 邻接表 存储无向图结构。
  2. 找到 Bob 的路径：
    • Bob 只能沿 唯一的一条路径 从 bob 走到 0，我们使用 DFS（深度优先搜索） 找到 Bob 的路径，并记录 Bob 经过每个节点的时间步 bobPath[node]。
  3. DFS 计算 Alice 的最大收益：
    • Alice 选择一条路径，使得她的收益最大。Alice 的收益计算如下：
      • 如果 Alice 先到达 node，她可以获得 全部 amount[node]。
      • 如果 Bob 先到达 node，Alice 无法获得 amount[node]。
      • 如果 Alice 和 Bob 同时到达，Alice 只能获得 amount[node] / 2。
    • 由于 Alice 需要找到 从 0 号节点到叶子节点的最大收益路径，我们采用 DFS 进行收益计算。

复杂度分析

  • 时间复杂度：O(n)，遍历整棵树，执行两次 DFS（一次找到 Bob 路径，一次 Alice 计算收益）。
  • 空间复杂度：O(n)，存储邻接表 graph、Bob 访问路径 bobPath、DFS 递归栈。

代码

/**
 * @param {number[][]} edges
 * @param {number} bob
 * @param {number[]} amount
 * @return {number}
 */
var mostProfitablePath = function (edges, bob, amount) {
	let graph = {};
	for (let [a, b] of edges) {
		if (!graph[a]) graph[a] = [];
		if (!graph[b]) graph[b] = [];
		graph[a].push(b);
		graph[b].push(a);
	}

	// 记录 Bob 经过的路径
	const findBobPath = (node, path) => {
		path.push(node);
		visited.add(node);

		if (node == 0) {
			bobPath = new Map(path.map((node, i) => [node, i])); // 记录 Bob 经过的节点及步数
			return true; // 找到路径后终止搜索
		}

		for (let child of graph[node]) {
			if (!visited.has(child) && findBobPath(child, path)) {
				return true;
			}
		}

		path.pop();
		return false;
	};

	const findMaxIncome = (node, score, step) => {
		visited.add(node);

		if (bobPath.has(node)) {
			let bobStep = bobPath.get(node);
			if (step < bobStep) {
				score += amount[node];
			} else if (step === bobStep) {
				score += amount[node] / 2;
			}
		} else {
			score += amount[node];
		}

		if (graph[node].length == 1 && node !== 0) {
			maxIncome = Math.max(maxIncome, score);
		} else {
			for (let child of graph[node]) {
				if (!visited.has(child)) {
					findMaxIncome(child, score, step + 1);
				}
			}
		}

		visited.delete(node);
	};

	let visited = new Set();
	let bobPath;
	findBobPath(bob, []);

	let maxIncome = -Infinity;
	visited.clear();
	findMaxIncome(0, 0, 0);
	return maxIncome;
};

相关题目

题号标题题解标签难度力扣
909蛇梯棋[✓]广度优先搜索 数组 矩阵🟠🀄️open in new window 🔗open in new window
3241标记所有节点需要的时间树 深度优先搜索 图 1+🔴🀄️open in new window 🔗open in new window
Copyright © 2025 2xiao