Leetcode 2467. Most Profitable Path in a Tree

Jimmy   Feb 24, 2025   643 words   ~20 mins
#Array #Tree #Depth-First Search #Breadth-First Search #Graph

Table of Contents

題目資訊

題目敘述

有一棵無向樹，包含 nn 個節點，標記為從 00 到 n−1n - 1，根節點為節點 00。給定一個長度為 n−1n - 1 的二維整數數組 edges，其中 edges[i]=[ai,bi]edges[i] = [a_i, b_i] 表示在樹中節點 aia_i 和 bib_i 之間有一條邊。

在每個節點 ii 上都有一個門。你也會得到一個偶數整數數組 amount，其中 amount[i] 代表：

  • 如果 amount[i] 是負數，則表示打開節點 ii 的門所需的費用，或者，
  • 否則，打開節點 ii 的門取得的現金獎勵。

遊戲規則如下：

  • 起初，愛麗絲在節點 00，鮑伯在節點 bob。

  • 每秒，愛麗絲和鮑伯各自移動到相鄰的節點。愛麗絲移動到某個葉節點，而鮑伯移動到節點 00。

  • 對於他們路徑上的每個節點，愛麗絲和鮑伯要麼花錢打開該節點的門，要麼接受獎勵。需要注意的是：

    • 如果門已經開啟，則不需要費用，也沒有現金獎勵。
    • 如果愛麗絲和鮑伯同時到達該節點，他們將共享打開門的費用/獎勵。換句話說，如果打開門的費用是 cc，那麼愛麗絲和鮑伯各自支付 c/2c / 2。同樣的，如果門的獎勵是 cc，他們各自收到 c/2c / 2。

  • 如果愛麗絲到達一個葉節點，她會停止移動。同樣地，如果鮑伯到達節點 00，他會停止移動。需要注意的是，這些事件是相互獨立的。

返回如果愛麗絲走向最優葉子節點，她所能得到的最大淨收入。

範例 1:

範例 1

輸入: edges = [[0,1],[1,2],[1,3],[3,4]], bob = 3, amount = [-2,4,2,-4,6]
輸出: 6
解釋: 
上圖表示給定的樹。遊戲過程如下：
- 愛麗絲最初在節點 0，鮑伯在節點 3。他們打開各自節點的門。
  愛麗絲的淨收入現在是 -2。
- 愛麗絲和鮑伯都移動到節點 1。
  由於他們同時到達這裡，他們共同打開門並共享獎勵。
  愛麗絲的淨收入變為 -2 + (4 / 2) = 0。
- 愛麗絲移動到節點 3。由於鮑伯已經打開了它的門，愛麗絲的收入保持不變。
  鮑伯移動到節點 0，並停止移動。
- 愛麗絲移動到節點 4 並打開那裡的門。她的淨收入變為 0 + 6 = 6。
現在，愛麗絲和鮑伯都無法再移動，遊戲結束。
愛麗絲不可能獲得更高的淨收入。

範例 2:

範例 2

輸入: edges = [[0,1]], bob = 1, amount = [-7280,2350]
輸出: -7280
解釋: 
愛麗絲沿著路徑 0->1，鮑伯沿著路徑 1->0。
因此，愛麗絲只打開節點 0 的門。因此，她的淨收入是 -7280。

約束:

  • 2≤n≤1052 \leq n \leq 10^5
  • edges.length == n - 1
  • edges[i].length == 2
  • 0≤ai,bi<n0 \leq a_i, b_i < n
  • ai≠bia_i \neq b_i
  • edges 表示一棵有效的樹。
  • 1≤bob<n1 \leq bob < n
  • amount.length == n
  • amount[i] 是範圍 [−104,104][-10^4, 10^4] 的偶數整數。

直覺

這個問題描述了一個場景，愛麗絲（Alice）和鮑伯（Bob）正在一個無向樹中導航，分別從樹的兩端開始（Alice 從根節點，Bob 從一個特定的節點），他們的移動會影響愛麗絲所能獲得的淨收入。為了有效地找出最大化愛麗絲淨收入的最佳路徑，關鍵在於理解以下幾點：

  1. 樹的結構允許使用深度優先搜索（DFS）進行自然的遍歷。
  2. 每個節點上的成本（或報酬）的調整必須考慮愛麗絲和鮑伯的移動，以及可能的會合點。
  3. 這需要識別從鮑伯的起始位置到根節點的路徑，因為愛麗絲的收入計算取決於共享和孤立節點的影響。

解法

這個解法包含幾個關鍵步驟：

  1. 圖形表示和初始化：首先通過給定的邊列表將樹表示為鄰接表。這種數據結構對於像 DFS 這樣的圖遍歷算法是高效的。

  2. 清除節點連接：為了在不遇到循環的情況下進行樹遍歷，函數 clearNodeConnections 修改鄰接表以防止在 DFS 中回溯，這基本上將鄰接表轉變為以節點 0 為根的有向無環圖（DAG）。

  3. 確定鮑伯的路徑：下一步涉及識別鮑伯返回根節點（節點 0）的路徑。通過這樣做，我們可以相應地調整鮑伯訪問的每個節點處的 amount 陣列：

    • 對於路徑的前半段，節點會在 amount 陣列中被標記為零，因為它們完全受到鮑伯的影響。
    • 如果路徑的長度是奇數，鮑伯路徑中間的節點將其 amount 減半，反映同時受到鮑伯和愛麗絲的共同影響。

  4. 計算愛麗絲的最大淨收入：通過調整後的 amount 陣列，函數 calculateMaxIncome 執行 DFS，以探索從根到任何葉節點的所有可能路徑。對於每條路徑，我們累加考慮經過修改的 amount 值的愛麗絲淨收入，並跟踪達到的最大收入。

  5. 返回結果：最後，函數返回愛麗絲通過遵循最佳路徑所能獲得的最大淨收入。

該算法結合了使用 DFS 進行路徑探索和基於鮑伯移動的策略性修改節點 amount 值，從而有效地確定最大化愛麗絲淨收入的最佳路徑和調整。

程式碼

C++

class Solution {
public:
    // 幫助函數用於清除鄰接列表中的已訪問節點
    void clearNodeConnections(vector<vector<int>>& adj, int node) {
        for (int child : adj[node]) {
            adj[child].erase(remove(adj[child].begin(), adj[child].end(), node), adj[child].end());
            clearNodeConnections(adj, child);
        }
    }

    // 遞歸函數用於找到 Bob 的路徑並相應地修改 `amount`
    bool findBobPath(vector<vector<int>>& adj, int bob, vector<int>& amount, stack<int>& path, int node) {
        path.push(node);

        // 如果找到 Bob 的位置
        if (node == bob) {
            bool isPathLengthOdd = (path.size() & 1);

            // 調整 Bob 所經過路徑上的節點金額
            int halfPathSize = path.size() / 2;
            for (int i = 0; i < halfPathSize; i++) {
                amount[path.top()] = 0;
                path.pop();
            }

            // 如果路徑長度為奇數，則在中間節點共同分享金額
            if (isPathLengthOdd) {
                amount[path.top()] /= 2;
            }

            return true;
        }

        // 遍歷子節點
        for (int child : adj[node]) {
            adj[child].erase(remove(adj[child].begin(), adj[child].end(), node), adj[child].end());
            // 遞歸找到 Bob 的路徑
            if (findBobPath(adj, bob, amount, path, child)) return true;
        }

        path.pop();  // 回溯
        return false;
    }

    // 計算 Alice 可以獲得的最大淨收入
    int calculateMaxIncome(vector<vector<int>>& adj, vector<int>& amount, int node, int currentValue) {
        currentValue += amount[node];

        // 葉節點檢查
        if (adj[node].empty()) {
            return currentValue;
        }

        int maxIncome = INT_MIN;

        // 遍歷子節點以找到最大收入
        for (int child : adj[node]) {
            maxIncome = max(maxIncome, calculateMaxIncome(adj, amount, child, currentValue));
        }

        return maxIncome;
    }

    // 主函數用於確定 Alice 最賺錢的路徑
    int mostProfitablePath(vector<vector<int>>& edges, int bob, vector<int>& amount) {
        stack<int> path;
        vector<vector<int>> adj(amount.size());

        // 建立鄰接列表
        for (vector<int>& edge : edges) {
            adj[edge[0]].push_back(edge[1]);
            adj[edge[1]].push_back(edge[0]);
        }

        // 清除鄰接列表中的不必要節點連接
        clearNodeConnections(adj, 0);

        // 找到 Bob 的路徑並相應地調整金額
        findBobPath(adj, bob, amount, path, 0);

        // 計算並返回 Alice 最優路徑的最大淨收入
        return calculateMaxIncome(adj, amount, 0, 0);
    }
};

Python

class Solution:
    # 輔助函式來清除在邻接表中的已訪問節點
    def clearNodeConnections(self, adj, node):
        for child in adj[node]:
            adj[child].remove(node)
            self.clearNodeConnections(adj, child)

    # 遞迴函式來找到 Bob 的路徑並相應地修改 `amount`
    def findBobPath(self, adj, bob, amount, path, node):
        path.append(node)

        # 如果找到 Bob 的位置
        if node == bob:
            isPathLengthOdd = (len(path) & 1)

            # 調整 Bob 已經經過路徑上節點的 amount
            halfPathSize = len(path) // 2
            for _ in range(halfPathSize):
                amount[path.pop()] = 0

            # 如果路徑長度是奇數，在中間節點分享 amount
            if isPathLengthOdd:
                amount[path[-1]] //= 2

            return True

        # 遍歷子節點
        for child in adj[node]:
            adj[child].remove(node)
            # 遞迴找到 Bob 的路徑
            if self.findBobPath(adj, bob, amount, path, child):
                return True

        path.pop()  # 回溯
        return False

    # 計算 Alice 可以取得的最大淨收入
    def calculateMaxIncome(self, adj, amount, node, currentValue):
        currentValue += amount[node]

        # 葉節點檢查
        if not adj[node]:
            return currentValue

        maxIncome = float('-inf')

        # 遍歷子節點以找到最大收入
        for child in adj[node]:
            maxIncome = max(maxIncome, self.calculateMaxIncome(adj, amount, child, currentValue))

        return maxIncome

    # 主函式來決定 Alice 的最有利的路徑
    def mostProfitablePath(self, edges, bob, amount):
        path = []
        adj = [[] for _ in range(len(amount))]

        # 建立邻接表
        for edge in edges:
            adj[edge[0]].append(edge[1])
            adj[edge[1]].append(edge[0])

        # 清除在鄰接表中不必要的節點連接
        self.clearNodeConnections(adj, 0)

        # 找到 Bob 的路徑並相應調整 amount
        self.findBobPath(adj, bob, amount, path, 0)

        # 計算並返回 Alice 最佳路徑能獲得的最大淨收入
        return self.calculateMaxIncome(adj, amount, 0, 0)

複雜度分析

  • 時間複雜度: O(n)O(n)。這是因為在構建鄰接表的過程中，每個節點恰好被訪問一次，清除節點連接、尋找Bob的路徑以及計算Alice的最大可能淨收入，從而提供了一個與節點數量nn相關的線性遍歷。
  • 空間複雜度: O(n)O(n)。這個空間包括樹的鄰接表表示以及用於記錄Bob路徑的堆疊。這兩個數據結構都需要與節點數量nn成比例的存儲空間。

Disclaimer: All reference materials on this website are sourced from the internet and are intended for learning purposes only. If you believe any content infringes upon your rights, please contact me at csnote.cc@gmail.com, and I will remove the relevant content promptly.


Feedback Welcome: If you notice any errors or areas for improvement in the articles, I warmly welcome your feedback and corrections. Your input will help this blog provide better learning resources. This is an ongoing process of learning and improvement, and your suggestions are valuable to me. You can reach me at csnote.cc@gmail.com.