最大化硬币，使根到叶子路径和为正

引言

在这个问题中，我们给定一棵树，它有 N 个顶点，根节点在 node[0] 处。树的所有边由数组 edges[][] 给出。还有另一个数组 arr[]，它代表硬币[]。arr[] 的大小是 N。我们必须选择任意一个节点并收集该节点中存在的所有硬币。我们的主要任务是找到收集到的最大硬币数量。我们必须以这样一种方式完成任务：从根节点到任何叶子节点的路径和保持为正（从根节点到叶子节点的路径和是根节点和叶子节点之间简单路径上节点中存在的总硬币）。

让我们通过例子来理解这一点。

示例-1

输入

我们得到输入如下：

N = 6, A[] = {5, 2, 5, 2, 1, 1 }, edges[][2] = {{0, 1}, {0, 2}, {0, 3}, {2, 4}, {4, 5}}

输出

上述输入的输出是 11。

说明

这里我们必须从节点 1、2、3、4 和 5 收集硬币。总硬币 = 2 + 5 + 2 + 1 + 1 = 11。

由于根节点 0 为零，因此从根节点到任何叶子的任何路径都将是非零的。

示例-2

输入

我们得到输入如下：

N = 7, A[] = { 20, 10, 9, 7, 4, 3, 5 }, edges[][2] = { {0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 5}, {2, 6} }

输出

上述输入的输出是 40。

解释：我们可以从节点 0、2、3 和 4 收集硬币。总硬币 = 20 + 9 + 7 + 4 = 40

• 从 0 到 4 的路径和等于 10。
• 从 0 到 3 的路径和等于 10。
• 从 0 到 5 的路径和等于 3。
• 从 0 到 6 的路径和等于 5。

因此，从根节点 0 到任何叶子的路径和是非零的。

方法

为了解决上述任务，我们有以下思路。

观察

有两种方法可以创建子树根。第一种是收集子树根中可用的硬币或其所有后代中存在的所有硬币。但这种方法存在一个问题。问题是找到保持从根节点到任何叶子节点的路径和非零所需的最小硬币。

我们可以借助树形动态规划方法来解决这个问题。

为了存储从节点 v 到任何叶子节点的路径和保持所需的最小硬币，我们必须借助 DP[V]。

转换： dp[v] = min(A[v], ∑dp[ui])

分步算法

为了解决这个问题，我们必须遵循以下步骤。

1. 首先，我们必须声明邻接列表 adj[N]，然后我们必须通过迭代 N - 1 条边来填充邻接列表。
2. 然后，我们必须声明 DP[] 数组，此数组的长度为 N。
3. 然后，我们必须声明 dfs 函数。此函数接受两个参数。这些参数是输入 v 节点和 p，其父节点。
   • 然后我们必须遍历所有子节点 u，然后我们必须计算 dp[v] = ∑dp[ui]。
   • 基本情况是，如果 v 旁边只有一个元素，那么我们必须将 dp[v] 更新为 A[v]。如果不是，那么我们必须将 dp[v] = min(dp[v], A[v])。
4. 然后，我们必须调用 dfs(0, -1) 函数。
5. 然后，我们必须声明一个变量，该变量存储 v 的每个节点上存在的所有硬币的总和。
6. 然后我们必须返回 totalCoins - dp[0]。

让我们借助编程语言来看看上面的算法。

C++ 中的实现

输出

说明

在上面的代码中，我们已经实现了算法。此外，我们还创建了 dfs 函数。我们用 C++ 编程语言实现了整个逻辑。

Java 实现

输出

说明

在上面的代码中，我们已经实现了算法。此外，我们还创建了 dfs 函数。我们用 Java 编程语言实现了整个逻辑。

时间复杂度

这种方法的时间复杂度是 O(N)，其中 N 表示树中的节点数。

空间复杂度

这种方法的空间复杂度是 O(N)。