最大路径和

题目描述

给定一棵完全二叉树，每个节点都有一定的价值，求所有从根节点到叶子节点的路径中，哪条路径的价值最大？路径的价值为路径上包含的所有节点的价值和。

输入格式

第一行 输入一个整数 $n$，表示树中的节点个数 接下来输入 $n$ 个整数，每个整数表示一个节点的编号，结点编号是按照完全二叉树的一维数组存储方式存储，这 $n$ 个点就表示一棵完全二叉树。例如：第一个数为根节点的编号，第二个数为根节点的左儿子的编号，第三个数为根节点右儿子的编号 接下来 $n$ 行每行一个整数，第 $i$ 个整数表示编号为 $i$ 的节点的价值。

输出格式

一个整数，表示价值和。

3
3 1 2
1
1
1

2

提示

#### 数据范围： $0\le n\le 100$，$0\le value，index\le 100$

来源

童程童美