题目内容

调用栈指从主函数执行到某个函数的调用路径，

如 $A$->$B$ ，经过这条调用栈到达的其他调用栈称为其子调用栈，如 $A$->$B$->$D$ 是 $A$->$B$ 的子调用栈；

使用某性能分析工具对软件运行过程中的调用栈进行采样分析，得到的热点调用栈数据为树形结构。

树的每个节点代表一条调用栈，子节点为父节点的子调用栈，每个节点有一个数值为采样到该调用栈的样本数量。

现需要刷新各节点的数值为包含其子调用栈的总样本数量，请编码实现。

数的层序遍历，指的是从上到下遍历每层，每层从左到右遍历各节点；为了标识子节点关系，对于 $N$ 个节点的树的层序遍历，插入 $N$ 个 $-1$ ，第 $i$ 个 $-1$ 和第 $i+1$ 个 $-1$ 中间的节点序列为第 $i$ 个节点的子节点序列，根节点为第 $1$ 个节点;

输入描述

第一行为树的总节点数量 $N$ ，取值范围 $[1，1000]$ ；

第二行为树的序列化输入，采用层序遍历，共 $2N$ 个数据，包括 $N$ 个节点的样本数和 $N$ 个节点的子节点序列的分隔符(参见示例)；

各节点样本数取值范围 $[0，10000]$ ；

输出描述

输出刷新各节点数值后的树，与输入格式保持一致。

样例1

输入

6
5 -1 2 3 8 -1 -1 1 7 -1 -1 -1

输出

26 -1 2 11 8 -1 -1 1 7 -1 -1 -1

说明

第一行表示树一共有 $6$ 个节点:

第二行为按照层序遍历的序列化输入，共 $12$ 个数据(含 $6$ 个节点的样本数和 $6$ 个节点的子节点序列的分隔符)，含义分别为：

• 5：第一个节点(即根节点)样本数为5；
• -1：分隔第一个节点(即根节点)的子节点序列；
• 2：第二个节点的样本数为2，它是第一个节点(即根节点)的第一个子节点；
• 3：第三个节点的样本数为3，它是第一个节点(即根节点)的第二个子节点；
• 8：第四个节点的样本数为8，它是第一个节点(即根节点)的第三个子节点；
• -1：分隔第二个节点的子节点序列；后续无有效数值，表示该节点无子节点；
• -1：分隔第三个节点的子节点序列；
• 1：第五个节点的样本数为1，它是第三个节点的第一个子节点；
• 7：第六个节点的样本数为7，它是第三个节点的第二个子节点；
• -1：分隔第四个节点的子节点，后续无有效数值，表示该节点无子节点；
• -1：分隔第五个节点的子节点，后续无有效数值，表示该节点无子节点；
• -1：分隔第六个节点的子节点，后续无有效数值，表示该节点无子节点；

构造输入树形结构：

根据树形结构计算各节点包含子节点的样本数:

调用栈 $A$->$C$ 有子调用栈 $A$->$C$->$E$ 和 $A$->$C$->$F$ ，其包含子调用栈的样本数量为 $3+1+7=11$；

根节点调用栈 $A$ 包含了调用栈 $A$->$B$、$A$->$C$ 和 $A$->$D$，其包含子调用栈的样本数量为 $5+2+11+8=26$;

刷新后的热点调用栈树:

按照层序遍历序列化输出:

26 -1 2 11 8 -1 -1 1 7 -1 -1 -1