题目内容

调用栈指从主函数执行到某个函数的调用路径，如 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