Question

2467. Most Profitable Path in a Tree

中文文档

Description

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 <= 105
• 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 [-104, 104].

Solutions

Solution 1: Two DFS Traversals

According to the problem, we know that Bob's moving path is fixed, that is, starting from node $bob$ and finally reaching node $0$. Therefore, we can first run a DFS to find out the time it takes for Bob to reach each node, which we record in the array $ts$.

Then we run another DFS to find the maximum score for each of Alice's moving paths. We denote the time for Alice to reach node $i$ as $t$, and the current cumulative score as $v$. After Alice passes node $i$, the cumulative score has three cases:

1. The time $t$ for Alice to reach node $i$ is the same as the time $ts[i]$ for Bob to reach node $i$. In this case, Alice and Bob open the door at node $i$ at the same time, and the score Alice gets is $v + \frac{amount[i]}{2}$.
2. The time $t$ for Alice to reach node $i$ is less than the time $ts[i]$ for Bob to reach node $i$. In this case, Alice opens the door at node $i$, and the score Alice gets is $v + amount[i]$.
3. The time $t$ for Alice to reach node $i$ is greater than the time $ts[i]$ for Bob to reach node $i$. In this case, Alice does not open the door at node $i$, and the score Alice gets is $v$, which remains unchanged.

When Alice reaches a leaf node, update the maximum score.

The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the number of nodes.

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
}