解题思路

本题给出的是一棵按完全二叉树层序遍历存储的目录树。

设总节点数为：

$N = 2^n - 1$

数组中每个位置表示一个目录节点：

题目内容

现在有一个 $n$ 层目录的文件系统，每个目录可以有多个文件和至多两个子目录（完全二叉树）。现在需要对同一层的目录进行压缩处理。当前仅知道每个目录下的文件大小，需要统计每个目录 (含子目录) 的总大小。

目录大小统计规则：给定一个目录的大小为$10$，该目录还有两个子目录，大小分别为$3$和$5$，则统计的该目录大小为$18$

输入描述

输入包含两行：

第一行为目录的层数 $n$，取值范围：$1<=n<=10$

第二行为一个基于二叉树层序遍历给出的第 $0-(n-1)$层各目录文件的大小一维数组，数组的每个元素 $m [i]$ 为整型，且$-1<=m[i]<=10$。

• $-1$表示该节点为空

• $0$表示该节点无文件但可能有子目录

输入示例：

3 
1 2 -1 5 3

输出描述

基于二叉树层序遍历的统计后的每个目录总大小，如果节点为空则用 $- 1$表示。第 $n-1$ 层最后一个节点后的空节点应省略，不用输出。输出结果不能以空格结束。

11 10 -1 5 3

计算逻辑说明：

• 节点 $5$ 和节点 $3$：因为为无子节点，计算后的大小即为自己的大小；
• 节点$2$：存在两个子节点 $5$ 和 $3$，计算后的大小为自己大小 + 子节点大小，即 $2+5+3=10$；
• 节点 $1$：存在一个子节点 $2$，先由子节点计算新大小，再计算新节点 $1$ 的大小，即 $1+10=11$。

样例1

输入

3
1 -1 2 -1 -1 3

输出

6 -1 5 -1 -1 3

说明

商品对共现统计：

• ($1,2$):$1$ 次
• ($1,3$): $2$次（用户 $1$ 和用户 $5$）
• ($2,3$):$1$次
• ($2,4$):$1$ 次

查询：

• $T=1$：共现≥1 次的有全部 $4$ 对 →$4$个
• $T=2$：共现≥2 次的有 ($1,3$) → $1$个

说明：用户$2、4$ 只购买了$1$个商品，不生成商品对

样例2

输入

3
1 2 -1 5 3

输出

11 10 -1 5 3

说明