题解 | #打家劫舍(三)#

本题会有大规模测试用例，用深度优先搜索可能会超出迭代次数上限。也许可以通过手动指定迭代次数上限来解决这个问题，但我选择维护动态规划列表。

本质上和前两道打家劫舍没有什么区别，难度虚高了。

n = int(input())
pts = list(map(int, input().split()))  # points
fas = list(map(int, input().split()))  # fathers

# 建树：sons[idx]是idx的子节点。节点编号从0开始。
sons = dict()
for idx in range(1,n):
    fa = fas[idx] - 1
    if fa in sons:
        sons[fa] += [idx]
    else:
        sons[fa] = [idx]

dfs = [0 for idx in range(n)]
# 初始化：叶子结点
for idx in range(n):
    if idx not in sons:
        dfs[idx] = pts[idx]
        
# 迭代：同一般“打家劫舍”
for idx in range(n)[::-1]:
    # y:偷这家，所以用这家的得分加上所有孙子节点的得分之和；n:不偷这家，得分等于子节点得分之和
    y,n = pts[idx],0
    if idx not in sons:
        continue
    for son in sons[idx]:
        n += dfs[son]
        if son in sons:
            y += sum([dfs[gson] for gson in sons[son]])
    dfs[idx] = max(y, n)

print(dfs[0])