整体分三步：还原二叉树 → 非递归后序处理（先规则一切除、后规则二归并）→ 层序输出并统计节点数与深度。
还原二叉树。 节点净功率取值两两不同，先用中序序列建立「值 → 中序下标」的映射。用显式栈模拟递归：栈帧记录当前子树在前序中的起点 pl、中序区间 [il, ir]、父节点编号 par 以及自己是父节点的左孩子还是右孩子。弹出一帧后，前序起点的值就是当前子树的根，查映射得到它在中序中的位置 k，左子树大小为 k - il，于是左子树对应前序 [pl+1, pl+k-il]、中序 [il, k-1]，右子树对应前序 [pl+k-il+1, ...]、中序 [k+1, ir]。把两个子问题压栈即可，避免递归在链状树上爆栈。直接用中序下标当节点编号，节点值就是中序序列本身。
规则一（越限隔离）。 用带状态位的显式栈做后序遍历：栈帧 (u, par, side, state)，state=0 表示首次进入，state=1 表示左右子树都已处理完。进入 u 时先算供电裕度 s(u)=s(par)+val(u)：若 s(u)<L 或 s(u)>R，直接把父节点指向 u 的指针置空（若 u 是根则整棵树置空），并不再展开它的后代，这就等价于「整棵子树一次性切除」；否则压入 state=1 帧和两个孩子的 state=0 帧。由于 state=1 帧先于孩子帧入栈、后于孩子帧出栈，规则一必然在每个节点的归并之前完成。
规则二（串联归并）。 在 state=1 帧里对 u 循环判断：若 u 恰好有一个孩子 c（没有孩子或有两个孩子都停止），且 u 与 c 同号（都大于 0 或都小于 0；只要有一方为 0 就视为不同号），则把 c 的值加到 u 上，并让 u 继承 c 的左右孩子，然后继续用新的值重复判断。每次归并都让树上少一个节点，总归并次数不超过 n，不会退化。
某城市的配电网络被抽象为一棵二叉树，每个节点代表一个配电台区，节点的整数值表示该台区的净功率（单位：kW）。正数表示向线路注入功率，负数表示从线路取用功率，0 表示功率平衡。
定义节点 u 的供电裕度 s(u) 为根节点到节点 u 的路径上所有节点净功率之和（包含路径两端）。给定安全区间 [L,R]，需要按照以下规则对配电树进行化简：
规则一（越限隔离）：若 s(u)<L 或 s(u)>R，则删除节点 u 及其整棵子树，不再处理其后代。
规则二（串联归并）：若节点 u 在左右子树化简后恰好只有一个子节点 v，且两节点的值同为正数或同为负数，则将二者归并为一个节点。归并后的节点占据 u 原来的位置，值为两节点值之和，左右子节点分别为 v 原来的左右子节点。归并后继续检查该节点是否满足归并条件，直到无法归并为止。值为 0 的节点不能参与归并。
处理顺序：对每个节点，先执行规则一；若节点未被删除，则依次处理其左子树和右子树，最后对当前节点执行规则二。供电裕度始终依据原始树计算，归并后不再重新进行越限判定。
给定配电树的前序遍历、中序遍历及安全区间 [L,R]，输出化简后配电树的层序遍历序列、节点数和最大深度。
节点数量满足 1≤n≤105。
节点净功率 ai 为整数，满足 −106≤ai≤106。
所有节点的净功率值两两不同，输入保证前序遍历和中序遍历对应同一棵二叉树。
L 和 R 为整数，满足 −1011≤L≤R≤1011。
分档：
第一行：化简后配电树的层序遍历序列，从根节点开始，逐层从左到右输出，整数之间用一个空格分隔；若树为空，则输出 null。
第二行：两个整数 m 和 d，分别表示化简后配电树的节点数和最大深度，以一个空格分隔。根节点深度为 1，空树的节点数和最大深度均为 0。
输入
6 2 1 -5 -3 -4 -2
-5 1 2 6 -3 -4 -2
-20 20
输出
6 3 -9 -5
4 3
说明
原始配电树结构如下：
6
/ \
2 -3
/ \
1 -4
/ \
-5 -2
所有节点的供电裕度均位于 [−20,20] 内，无节点被删除。
左子树中，节点 2 与 1 归并为 3，其子节点 −5 保留。右子树中，节点 −4 与 −2 归并为 −6，再与节点 −3 归并为 −9。
化简后的配电树如下：
6
/ \
3 -9
/
-5
层序遍历为 6,3,−9,−5，共 4 个节点，最大深度为 3。
输入
5 3 -9 4 8 10
-9 3 4 5 8 10
0 20
输出
5 7 8
3 2
说明
原始配电树结构如下：
5
/ \
3 8
/ \ \
-9 4 10
节点 −9 的供电裕度为 −1<0，节点 10 的供电裕度为 23>20，因此两者被删除。
节点 3 与其剩余子节点 4 归并为 7。节点 8 成为叶子节点，根节点 5 保留两个子节点。
化简后的配电树如下：
5
/ \
7 8
层序遍历为 5,7,8，共 3 个节点，最大深度为 2。
输入
3 6 0 5
3 6 0 5
0 100
输出
9 0 5
3 3
说明
原始配电树是一条仅包含右孩子的链：
3
\
6
\
0
\
5
所有节点的供电裕度均在安全区间内。节点 3 与 6 同为正数，归并为 9；由于节点 0 不能参与归并，后续节点保持不变。
化简后的配电树如下：
9
\
0
\
5
层序遍历为 9,0,5，共 3 个节点，最大深度为 3。
输入
-2 7 3 1 5
3 7 1 -2 5
1 100
输出
null
0 0
说明
原始配电树结构如下：
-2
/ \
7 5
/ \
3 1
根节点的供电裕度为 −2<1，触发越限隔离，整棵树被删除。
化简后树为空：
null
节点数和最大深度均为 0。
输入
4 -9 -8
-9 4 -8
1 10
输出
4
1 1
说明
原始配电树结构如下：
4
/ \
-9 -8
根节点 4 的供电裕度位于安全区间内。其左、右孩子的供电裕度分别为 −5 和 −4，均低于下界 1，因此被删除。
化简后的配电树如下：
4
层序遍历为 4，节点数和最大深度均为 1。
In following contests:
© CodeFun2000 · 使用条款
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册