c - 如何找到树中节点的最大总和

Question

我有两个数组，一个定义节点的关系，另一个给出节点的值。

arr1={0,1,1,1,3,3,4}
arr2={22,100,3,3,4,5,9}

arr1 定义关系，即根节点是第一个元素，节点 2,3 和 4 的父节点是节点 1，节点 5 和 6 的父节点是根节点 3，节点 7 的父节点是节点 4。

arr2给出节点的值，节点1的值为22，节点2的值为100。

我必须找到节点的最大总和，使得所有包含的节点都没有父节点或祖父节点关系。

示例输入:

a[i]=[0,1,1,1,3,3,6,6]
b[i]=[1,2,3,4,5,100,7,8]

output: 111

我是 DS 和 ALGO 的新手，甚至想不出解决方案。需要帮助谢谢。任何类型的帮助都可以。

Answer 1

您可以使用动态编程 来解决它。考虑一个数组 dp[]，它存储每个顶点及其子树的答案。

现在 DP 的状态是，

dp[currentVertex] = max(sum of all children's dp[] ,
                        b[currentVertex] + sum of all vertices' dp[] whose 
                        greatGrandParent is currentVertex])

您需要使用自下而上的方法构建DP 表。所以从树叶开始。

经过所有计算，答案将是 dp[root]。