Chino 的树学

有一棵满二叉树（每个非叶子结点都有两个孩子），一共有 n 层（根在第 1 层，叶子在第 n 层）。 树上每个结点都有一个权值（整数）。我们想从根结点出发，走到某个叶子结点，让沿途经过的结点权值之和尽可能大，问这个最大和是多少。

给你的输入不是边，而是这棵树的先序遍历（preorder）： 先序顺序是 ——「访问当前结点 → 遍历左子树 → 遍历右子树」。 因为树是满二叉树，结点总数一定是 \(2^n - 1\)，所以先序序列里刚好有这么多数字。

特殊的"Chino 树"性质（不用被吓到）

题目还说这棵树有个对称性质：对每个非叶子结点，它的"左孩子的右孩子"和"右孩子的左孩子"这两个结点的权值相同，而且它们底下的整棵子树也一模一样。

直观理解： 每个分叉处的"中间两只孙子"完全对称（值一样、结构一样）。 这个性质保证了这棵树非常规整，但对"求根到叶子的最大路径和"这件事，你不需要特意用这个性质，按正常的"先序建树 + 取最大根到叶路径和"就能做。

你需要输出什么？

一条从根走到任意一个叶子的路径，使得经过结点的权值总和最大。输出这个最大总和。

输入格式

• 第 1 行：一个整数 n —— 树的层数（根为第 1 层，叶为第 n 层）。
• 第 2 行：\(2^n - 1\) 个整数，表示这棵树的先序遍历结果（从根开始，先当前、再左、再右）。

输出格式

• 一行，一个整数：从根到某个叶子的最大路径和。

样例 1

输入

3
6 17 43 55 20 55 38

输出

81

解释（示意） 这是一棵 3 层的满二叉树，共 7 个结点。先序序列的第一个数 6 是根； 接着是整棵左子树的先序；再接着是整棵右子树的先序。 在所有根到叶的路径里，最大和为 81。

样例 2

输入

4
6 20 72 61 26 55 26 7 17 55 26 7 38 7 35

输出

159

小贴士（帮助理解/实现）

• 怎么从先序序列恢复树并算最大和？ 因为是满二叉树且层数 n 已知，我们可以用一个递归函数按先序顺序"读数"：

  • 读到当前结点的值；
  • 如果还没到第 n 层，就递归读左子树、再读右子树；
  • 返回"当前结点值 + max(左子树最大根到叶路径和, 右子树最大根到叶路径和)"；
  • 最终返回的就是整棵树的答案。
• 数据可能比较大，结果请用 64 位整型（如 C++ 的 long long）保存。

图里写的"C 和 D 的值相同且子树相同"的特殊性质，是为了描述这类"Chino 树"的规整性。 但你不需要专门用这个性质去推什么结构；只要按先序读出一棵满二叉树，然后做"根到叶最大路径和"，就能得到答案。