K 整除組件的最大數量

2872。 K 整除分量的最大數量

難度：難

主題：樹，深度優先搜尋

有一個無向樹，有 n 個節點，標示為 0 到 n - 1。給定整數n 和長度為n - 1 的二維整數數組邊，其中Edges[i] = [a_i, b_i] 表示節點a_i 和之間有一條邊b_i 在樹中。

您還會得到一個長度為 n 的 0 索引 整數數組值，其中values[i] 是與第 i^th 節點關聯的值，以及一個整數 k。

樹的有效分割是透過從樹中刪除任何一組邊（可能是空的）來獲得的，這樣生成的組件都具有可被k整除的值，其中值連接組件 的值是其節點值的總和。

傳回任何有效分割中組件的最大數量。

範例1：

• 輸入： n = 5，邊= [[0,2],[1,2],[1,3],[2,4]]，值= [1,8,1,4 ,4], k = 6
• 輸出： 2
• 解釋： 我們刪除連接節點 1 和 2 的邊。產生的分割是有效的，因為：
  • 包含節點 1 和 3 的組件的值為values[1]values[3] = 12。
  • 包含節點 0、2、4 的元件的值為values[0]values[2]values[4] = 6。
  • 可以證明，沒有其他有效的分割具有超過 2 個連通分量。

範例2：

• 輸入： n = 7，邊= [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6] ]，值= [3,0,6,1,5,2,1]，k = 3
• 輸出： 3
• 解釋： 我們刪除連接節點 0 和 2 的邊，以及連接節點 0 和 1 的邊。由此產生的分割是有效的，因為：
  • 包含節點0的元件的值為values[0] = 3。
  • 包含節點 2、5、6 的分量的值為values[2]values[5]values[6] = 9。
  • 包含節點 1、3、4 的元件的值為values[1]values[3]values[4] = 6。
  • 可以證明，沒有其他有效的分割具有超過 3 個連通分量。

約束：

• 1 4
• edges.length == n - 1
• 邊[i].length == 2
• 0
• values.length == n
• 0 9
• 1 9
• 值的總和可被 k 整除。
• 產生輸入，使得邊代表有效的樹。

提示：

1. 樹的根位於節點 0。
2. 如果葉子節點不能被 k 整除，則它必須與其父節點位於同一元件中，因此我們將其與其父節點合併。
3. 如果葉節點可被 k 整除，則它將位於自己的組件中，因此我們將其與其父節點分開。
4. 在每一步中，我們要麼砍掉一個葉節點，要麼合併一個葉節點。樹上的節點數減少 1。重複這個過程，直到只剩下一個節點。

解：

我們可以實現深度優先搜尋（DFS）方法來探索樹，追蹤元件的值，並找到有效分割的最大數量。

要點：

• 樹結構：我們正在使用無向樹，其中每個節點都有一個關聯的值。我們需要找到透過分裂樹可以獲得的最大連通分量數，使得每個分量的值的總和可以被 k 整除。
• DFS 遍歷： 我們使用深度優先搜尋 (DFS) 來遍歷樹併計算子樹和。
• 整除性檢查：計算子樹的和後，如果它能被k整除，則表示該子樹本身可以被視為有效組件。
• 邊移除：移除連接子樹和不能被 k 整除的節點的邊，我們可以最大化有效組件的數量。

方法：

1. 樹表示： 將邊列表轉換為鄰接列表來表示樹。
2. DFS遍歷：從節點0開始，遞歸計算每個子樹中的值的總和。如果總和可被 k 整除，我們可以將該子樹從其父樹中分離出來，從而有效地形成一個有效的組件。
3. 全域計數：維護一個全域計數器（結果），追蹤切割邊緣形成的有效組件的數量。
4. 最終檢查： 在 DFS 遍歷結束時，確保根的子樹總和能被 k 整除，則算作有效分量。

計劃：

1. 輸入解析： 將輸入轉換為可用的形式。具體來說，為樹創建一個鄰接列表表示。
2. DFS 函數： 寫一個遞歸函數 dfs(node)，計算以節點為根的子樹中的值總和。如果該總和可被 k 整除，則增加結果計數器並透過傳回 0 來「剪下」邊緣，以防止合併回父級。
3. 從Root開始DFS：呼叫dfs(0)，然後檢查結果的最終值。

解決步驟：

1. 建構樹：將邊列表轉換為鄰接列表，以便於遍歷。
2. 初始化存取數組：使用存取數組來確保我們不會重新訪問節點。
3. DFS遍歷：從節點0開始進行DFS。對於每個節點，計算其子樹的值的總和。
4. 檢查整除性：如果子樹的總和可被 k 整除，則增加結果並將子樹總和重設為 0。
5. 最終組件檢查： DFS 遍歷之後，檢查整個樹（以節點 0 為根）的總和是否可被 k 整除，並在必要時將其作為單獨的組件進行處理。

讓我們用 PHP 實作這個解決方案：2872。 K 可整除分量的最大數量

解釋：

1. 樹結構：我們建立一個鄰接表來表示樹結構。每條邊連接兩個節點，我們使用這個鄰接表來遍歷樹。
2. DFS 遍歷： DFS 函數遞歸計算以每個節點為根的子樹的總和。如果子樹的總和可被 k 整除，我們將結果遞增並將子樹視為單獨的有效元件。
3. 傳回子樹總和：對於每個節點，DFS 函數傳回其子樹的值的總和。如果子樹可被 k 整除，我們會透過返回 0 總和來有效地「切割」邊緣，從而防止進一步與父節點合併。
4. 最終檢查： 在 DFS 結束時，我們確保如果整棵樹的總和能被 k 整除，則它算作有效組件。

演練範例：

範例1：

輸入：

• n = 5，邊 = [[0,2],[1,2],[1,3],[2,4]]，值 = [1,8,1,4,4]，k = 6。

DFS 從節點 0 開始：

• 節點 0：子樹總和 = 1
• 節點 2：子樹和 = 1 1 4 = 6（可被 6 整除，因此我們可以剪掉這條邊）
• 節點1：子樹和= 8 4 = 12（能被6整除，剪掉這條邊）
• 最終組件數 = 2。

範例2：

輸入：

• n = 7，邊緣= [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]，值= [3,0 ,6,1,5,2,1],k = 3.

DFS 從節點 0 開始：

• 節點 0：子樹總和 = 3
• 節點2：子樹和= 6 2 1 = 9（能被3整除，剪掉這條邊）
• 節點 1：子樹和 = 0 5 = 5（不能被 3 整除，合併這個和）
• 最終組件數 = 3。

時間複雜度：

• DFS 時間複雜度： O(n)，其中 n 是節點數。我們訪問每個節點一次，並在每個節點執行恆定時間操作。
• 空間複雜度： 鄰接表、存取陣列和遞歸堆疊的 O(n)。

因此，總體時間和空間複雜度為 O(n)，使得此方法對於給定的問題限制非常有效。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是K 整除組件的最大數量的詳細內容。更多資訊請關注PHP中文網其他相關文章！