每年夏天,为了应对台风的袭击,树王国都要对王国中的树进行加固。
受到经济危机的影响,树王国出售了大量建材,现在,树王国的材料恰好只够加固树王国所有公园里的树木。
树王国有 座公园和仓库,它们以满二叉树的形状排列。树的每一条边是一条道路。方便起见,我们给每个公园和仓库一个权值。当该值为负时,该地为一个仓库,这个值的绝对值代表该仓库存放的材料可以加固的树木的数量;当该值为正时,该地为一个公园,这个值代表该公园内树木的数量。为了加固树木,树王国需要雇佣帕鲁把建材从仓库搬运到公园。加固树木本身不需要消耗任何帕鲁。
每将可以加固一棵树的建材搬运过一条道路需要消耗雇佣一名帕鲁。现在,树王国的国王希望你能找到最少需要雇佣多少帕鲁才能加固好所有树木。
第一行为一个整数 ,代表公园和仓库构成的满二叉树的深度。
第二到 行中,第 行有 个整数,其中第 行第 个数 表示对应满二叉树的第 层从左往右第 座公园或仓库的权值。
一个整数,表示最少需要的帕鲁数量。
3 -7 12 5 -4 1 -2 -5
23
一种的可行的最少方案如下:
向 搬运 个单位的建材,经过 条道路,需要雇佣 名帕鲁;
先向 搬运 个单位的建材,经过 条道路,需要雇佣 名帕鲁;
总共需要雇佣的帕鲁数量为:。
答案保证小于等于