如何求解树中无父子节点的最大节点和（给定节点关系与值数组）

这个问题本质是树的最大独立集问题——在一棵树上挑选若干节点，要求任意两个选中节点不存在直接父子关系，最终求这些节点的权值最大和。下面我一步步拆解思路，再给出可运行的代码实现。

先理清楚节点关系与值 #

首先我们把题目里的对应关系明确下来，避免混淆：

• 节点编号：1~7（对应arr2的索引0到6）
• 节点值：
  • 节点1: 22，节点2: 100，节点3: 3，节点4: 3
  • 节点5:4，节点6:5，节点7:9
• 父子结构：
  • 根节点是1（父节点为0）
  • 节点2、3、4的父节点是1
  • 节点5、6的父节点是3
  • 节点7的父节点是4

动态规划核心思路 #

我们用动态规划（DP）来解决，给每个节点定义两种状态：

• dp[u][0]：不选节点u时，以u为根的子树能拿到的最大和
• dp[u][1]：选节点u时，以u为根的子树能拿到的最大和

状态转移规则 #

1. 如果选了节点u，那它的所有子节点都不能选，所以：

   dp[u][1] = 节点u的权值 + 所有子节点v的dp[v][0]之和
   

2. 如果不选节点u，那每个子节点都可以选或不选，我们取每个子节点两种状态的最大值相加：

   dp[u][0] = 所有子节点v的max(dp[v][0], dp[v][1])之和
   

Python代码实现 #

先构建树的邻接表（存储每个节点的子节点），再通过递归的方式计算DP值：

# 题目给定的输入
arr1 = [0, 1, 1, 1, 3, 3, 4]
arr2 = [22, 100, 3, 3, 4, 5, 9]

# 构建树结构：key是父节点，value是子节点列表
tree = {}
for idx in range(len(arr1)):
    child_node = idx + 1  # 子节点编号对应索引+1
    parent_node = arr1[idx]
    if parent_node not in tree:
        tree[parent_node] = []
    tree[parent_node].append(child_node)

# 递归计算每个节点的DP值
def calculate_dp(node):
    # 初始化两种状态：不选当前节点为0，选当前节点为自身值
    dp_not_select = 0
    dp_select = arr2[node - 1]
    
    # 遍历所有子节点，递归计算子节点的DP值
    if node in tree:
        for child in tree[node]:
            child_not_select, child_select = calculate_dp(child)
            # 不选当前节点时，累加子节点的最优解
            dp_not_select += max(child_not_select, child_select)
            # 选当前节点时，只能累加子节点不选的情况
            dp_select += child_not_select
    
    return dp_not_select, dp_select

# 根节点是1（父节点为0的节点）
root = 1
max_total = max(calculate_dp(root))
print("满足条件的最大节点和为:", max_total)

结果验证 #

运行代码后输出的最大和是118，对应的选中节点是：节点2（100）、节点5（4）、节点6（5）、节点7（9），总和为100+4+5+9=118。这确实是最优解——如果选根节点1，最多只能拿到22+4+5+9=40，远不如选节点2加上它的所有“孙节点”划算。

内容的提问来源于stack exchange，提问作者crownedlake