2872。 K 整除分量的最大數(shù)量

難度：難

主題：樹，深度優(yōu)先搜尋

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

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

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

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

範例1：

• 輸入： n = 5，邊= [[0,2],[1,2],[1,3],[2,4]]，值= [1,8,1,4 ,4], k = 6
• 輸出： 2
• 解釋： 我們刪除連接節(jié)點 1 和 2 的邊。產(chǎn)生的分割是有效的，因為：
  • 包含節(jié)點 1 和 3 的組件的值為values[1]values[3] = 12。
  • 包含節(jié)點 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
• 解釋： 我們刪除連接節(jié)點 0 和 2 的邊，以及連接節(jié)點 0 和 1 的邊。由此產(chǎn)生的分割是有效的，因為：
  • 包含節(jié)點0的元件的值為values[0] = 3。
  • 包含節(jié)點 2、5、6 的分量的值為values[2]values[5]values[6] = 9。
  • 包含節(jié)點 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 整除。
• 產(chǎn)生輸入，使得邊代表有效的樹。

提示：

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

解：

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

要點：

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

方法：

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

計劃：

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

解決步驟：

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

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

解釋：

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

演練範例：

範例1：

輸入：

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

DFS 從節(jié)點 0 開始：

• 節(jié)點 0：子樹總和 = 1
• 節(jié)點 2：子樹和 = 1 1 4 = 6（可被 6 整除，因此我們可以剪掉這條邊）
• 節(jié)點1：子樹和= 8 4 = 12（能被6整除，剪掉這條邊）
• 最終組件數(shù) = 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 從節(jié)點 0 開始：

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

時間複雜度：

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

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

聯(lián)絡連結

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

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

• 領英
• GitHub

以上是K 整除組件的最大數(shù)量的詳細內(nèi)容。更多資訊請關注PHP中文網(wǎng)其他相關文章！