题目内容

在容器镜像管理系统中, 容器镜像通常采用堆叠方式管理和挂载, 为了减少镜像管理系统中重复的镜像层数量, 假定容器镜像层采用二叉树管理。镜像层二叉树节点描述镜像层大小, 节点的镜像完整大小为镜像层大小及其所有父节点镜像层大小之和。由于业务需要, 现在需要对系统中所有的客户镜像大小统计分析, 从小到大输出最大的 $K$ 个镜像大小; 输入为容器镜像二叉树前序遍历数组和中序遍历数组, 输出为最大的 $K$ 个镜像大小, 并按从小到大排序输出。

说明: 当镜像完整大小小于等于 $0$ 时, 则表示该镜像节点异常, 异常镜像节点需要剪枝; 例如: 节点 $A$ 有子节点 $B$ 和子节点 $C$, 如果节点 $A$ 完整镜像大小为 $0$, 则节点 $A$ 需要剪枝, 即节点 $A$、节点 $B$、节点 $C$均需要从镜像二叉树中删除。

输入描述

第一行: 容器镜像树前序遍历结果。

第二行: 容器镜像树中序遍历结果。

第三行: 需要统计的最大容器镜像个数, 取值范围为 [$1$,$1000$]。

说明:

1. 容器镜像树前序遍历、中序遍历结果中的数字表示当前镜像层大小, 取值范围为 [$-10000$,$10000$]。

2. 镜像层大小为负数时表示该层基于父镜像裁剪文件, 镜像层为正数时表示该层基于父镜像新增文件, $0$ 则表示镜像层未做任何更改或者裁剪文件大小与新增文件大小相等;

3. 节点规模数量 $\le 1000$。

4. 为了能够通过前序遍历和中序遍历还原唯一的镜像二叉树, 输入的各节点镜像层大小都不相同。

输出描述

从小到大输出最大的镜像大小。

说明:

1. 如果二叉树节点总数小于需要统计 $TOP$ 数量, 则从小到大输出所有镜像大小。

2. 如果二叉树剪枝后为空, 则输出 $null$。

样例1

输入

8 2 -3 9 5
2 8 9 -3 5
3

输出

10 10 14

说明

根据 $8\ 2\ -3\ 9\ 5$ 前序遍历, $2\ 8\ 9\ -3\ 5$ 中序遍历, 得到左图所示二叉树, 每个节点数字为对应镜像层大小; 每个节点镜像大小为自身节点镜像层大小加上所有父节点镜像层大小, 如右图所示为计算之后的各节点镜像实际大小。 一共有 $5$ 个镜像, 镜像大小分别是 $8$, $10$, $5$, $14$, $10$, 所以 $TOP3$ 从小到大排序为$10\ 10\ 14$。

样例2

输入

1 2 3 -5 5 6
2 1 3 5 -5 6
1

输出

4

说明

左图为输入的二叉树, 由于 $-5$ 节点计算出镜像完整大小为 $-1$, 小于等于 $0$, 因此属于非法节点, 需要剪枝处理, 剪枝后得到最右边的二叉树, 一共三个镜像, $TOP1$镜像大小为 $4$。