2467. Most Profitable Path in a Tree

SourceBiweekly Contest 91 Q3DifficultyMediumRating2053

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] = [a_i, b_i] indicates that there is an edge between nodes a_i and b_i 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⁵
edges.length == n - 1
edges[i].length == 2
0 <= a_i, b_i < n
a_i != b_i
edges represents a valid tree.
1 <= bob < n
amount.length == n
amount[i] is an even integer in the range [-10⁴, 10⁴].

Solutions

Solution 1: Two DFS Traversals

Thinking

Bob's path is the unique \(bob\to 0\) route; Alice walks from \(0\) to a leaf. At \(n\le 10^5\), a first DFS stores Bob's arrival time \(ts\) on that path.

A second DFS from \(0\) scores a node as half if times tie, full if Alice is earlier, and zero if later. Update the answer at leaves.

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:

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}\).
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]\).
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.

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
}

Solution 2: Two Explicit Stacks

Thinking

Bob follows the unique path from \(bob\) to the root \(0\), and Alice walks from \(0\) to a leaf. The answer is her maximum net income. With \(n\le 10^5\), recursion along a chain uses a call depth equal to the node count and overflows Python once the chain reaches length \(1000\). The path is unique, so the search does not need to return through every frame. A stack rooted at \(0\) records each parent, and walking those parents writes Bob's arrival time into \(ts\). Every other node keeps the sentinel \(n\). Alice's score at node \(i\) depends only on her time \(t\) and \(ts[i]\), so the second walk is a pre-order stack. A popped node adds half the gate, the whole gate, or nothing. A node whose only neighbor is its parent is a leaf, and that score updates the answer.

The tree has one path from \(bob\) to \(0\). An explicit stack walks the tree from node \(0\) and records each node's parent. Walking from \(bob\) along those parents then sets \(ts\) to the step \(t\) at which Bob arrives. Nodes that are not on this path keep the initial value \(n\), meaning Bob never opens them.

A second explicit stack moves Alice from \(0\) toward a leaf. Each frame stores a node, its parent, the arrival time \(t\), and the income \(v\) collected before entering the node. After node \(i\) is popped, the income has three cases:

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}\).
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]\).
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.

If \(i\) has only one neighbor and that neighbor is its parent, then \(i\) is a leaf and the current score updates the answer.