K 整除组件的最大数量-php教程-PHP中文网

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：

Maximum Number of K-Divisible Components

输入： 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：

Maximum Number of K-Divisible Components

输入： 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 整除。
生成输入，使得边代表有效的树。

提示：

树的根位于节点 0。
如果叶子节点不能被 k 整除，则它必须与其父节点在同一组件中，因此我们将其与其父节点合并。
如果叶节点可被 k 整除，则它将位于其自己的组件中，因此我们将其与其父节点分开。
在每一步中，我们要么砍掉一个叶子节点，要么合并一个叶子节点。树上的节点数减少 1。重复此过程，直到只剩下一个节点。

解决方案：

我们可以实现深度优先搜索（DFS）方法来探索树，跟踪组件的值，并找到有效分割的最大数量。

要点：

树结构：我们正在使用无向树，其中每个节点都有一个关联的值。我们需要找到通过分裂树可以获得的最大连通分量数，使得每个分量的值的总和可以被 k 整除。
DFS 遍历： 我们使用深度优先搜索 (DFS) 来遍历树并计算子树和。
整除性检查：计算子树的和后，如果它能被k整除，则表示该子树本身可以被视为有效组件。
边移除：通过移除连接子树和不能被 k 整除的节点的边，我们可以最大化有效组件的数量。

方法：

树表示： 将边列表转换为邻接列表来表示树。
DFS遍历：从节点0开始，递归计算每个子树中的值的总和。如果总和可被 k 整除，我们可以将该子树从其父树中分离出来，从而有效地形成一个有效的组件。
全局计数：维护一个全局计数器（结果），跟踪切割边缘形成的有效组件的数量。
最终检查： 在 DFS 遍历结束时，确保根的子树总和能被 k 整除，则算作有效分量。

计划：

输入解析： 将输入转换为可用的形式。具体来说，为树创建一个邻接列表表示。
DFS 函数： 编写一个递归函数 dfs(node)，计算以节点为根的子树中的值之和。如果该总和可被 k 整除，则增加结果计数器并通过返回 0 来“剪切”边缘，以防止合并回父级。
从Root开始DFS：调用dfs(0)，然后检查结果的最终值。

解决步骤：

构建树：将边列表转换为邻接列表，以便于遍历。
初始化访问数组：使用访问数组来确保我们不会重新访问节点。
DFS遍历：从节点0开始进行DFS。对于每个节点，计算其子树的值的总和。
检查整除性：如果子树的总和可被 k 整除，则增加结果并将子树总和重置为 0。
最终组件检查： DFS 遍历之后，检查整个树（以节点 0 为根）的总和是否可被 k 整除，并在必要时将其作为单独的组件进行处理。

让我们用 PHP 实现这个解决方案：2872。 K 可整除分量的最大数量

<?php
/**
 * @param Integer $n
 * @param Integer[][] $edges
 * @param Integer[] $values
 * @param Integer $k
 * @return Integer
 */
function maxKDivisibleComponents($n, $edges, $values, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * DFS Function
 *
 * @param $graph
 * @param $node
 * @param $parent
 * @param $values
 * @param $k
 * @param $ans
 * @return array|bool|int|int[]|mixed|null
 */
private function dfs($graph, $node, $parent, &$values, $k, &$ans) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1
$n = 5;
$edges = [[0,2],[1,2],[1,3],[2,4]];
$values = [1,8,1,4,4];
$k = 6;
echo maxKDivisibleComponents($n, $edges, $values, $k) . "\n"; // Output: 2

// Example 2
$n = 7;
$edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]];
$values = [3,0,6,1,5,2,1];
$k = 3;
echo maxKDivisibleComponents($n, $edges, $values, $k) . "\n"; // Output: 3
?>

登录后复制

解释：

树结构：我们构建一个邻接表来表示树结构。每条边连接两个节点，我们使用这个邻接表来遍历树。
DFS 遍历： DFS 函数递归计算以每个节点为根的子树的总和。如果子树的总和可被 k 整除，我们将结果递增并将子树视为单独的有效组件。
返回子树总和：对于每个节点，DFS 函数返回其子树的值的总和。如果子树可被 k 整除，我们会通过返回 0 之和来有效地“切割”边缘，从而防止进一步与父节点合并。
最终检查： 在 DFS 结束时，我们确保如果整棵树的总和能被 k 整除，则它算作有效组件。