你是一个经验丰富的小偷,经过上次在街边和湖边得手后你准备挑战一次自己,你发现了一个结构如二叉树的小区,小区内每个房间都存有一定现金,你观察到除了小区入口的房间以外每个房间都有且仅有一个父房间和至多两个子房间。 问,给定一个二叉树结构的小区,如之前两次行动一样,你无法在不触动警报的情况下同时偷窃两个相邻的房间,在不触动警报的情况下最多的偷窃金额。 1.如果输入的二叉树是 5 2 1 2 2 1 0 1 1 2 3 那么形状结构如下: 小区入口的房间的值是2 ,偷窃第一层2和第三层 2,1 是最优方案。 2.如果输入的二叉树是 3 3 2 10 0 1 1 那么形状结构如下: 样例2:小区入口的房间的值是3 ,偷窃第二层 2,10 是最优方案。 数据范围:二叉树节点数量满足 ,树上的值满足
输入描述:
第一行输入一个正整数 n 表示节点的数量。第二行输入 n 个正整数,其中第 i 个节点表示序号是 i 的节点的值。第三行输入 n 个整数,其中第 i 个数表示序号是 i 的节点的父节点的序号。(0表示是根节点)


输出描述:
输出最优方案的的偷窃金额。
示例1

输入

5
2 1 2 2 1
0 1 1 2 3

输出

5
示例2

输入

3
3 2 10
0 1 1

输出

12
加载中...