Recursive Walk Down a Hierarchical Rebate-Tier Tree
Recursive Walk Down a Hierarchical Rebate-Tier Tree
开始编码一张多档返利费率表被编码成 N 叉树。每个节点对应一个合格档位，携带 rate、threshold（解锁这一档需要的最小累计量），以及一个嵌套的 children 列表——只有先达成本档之后才会开放的子档。给定一个累计成交量 V，从 root 出发向下游走，每一层在剩余量仍能合格的子档里挑 threshold 最大的那个（也就是「最高档」），按它的 rate 对当前剩余量计返利，然后用剩余量减去这一层 threshold 后递归进入它的子档。总返利就是这一条 root-to-leaf 路径上每层贡献的累加。
实现 solution(tree: dict, volume: float) -> float。每个节点形如：
{"tier_name": str, "rate": float, "threshold": float, "children": list[node]}root 是哨兵（threshold = 0, rate = 0）——它本身不贡献返利，只是游走的入口。
递推式：
walk(node, remaining):
qualifying = [c for c in node.children if c.threshold <= remaining]
如果 qualifying 为空 或 remaining == 0:
return 0
chosen = argmax_{c in qualifying} c.threshold
return chosen.rate * remaining + walk(chosen, remaining - chosen.threshold)
solution(tree, V) = walk(tree, V)例子
solution({"tier_name": "root", "rate": 0.0, "threshold": 0.0, "children": [{"tier_name": "T1", "rate": 0.001, "threshold": 1000.0, "children": []}]}, 5000.0) 返回 5.0。一层费率表：T1 合格（threshold 1000 ≤ V=5000），返利 0.001 · 5000 = 5.0；T1 没有子档，递归终止。
solution({"tier_name": "root", "rate": 0.0, "threshold": 0.0, "children": [{"tier_name": "T1", "rate": 0.001, "threshold": 1000.0, "children": [{"tier_name": "T1a", "rate": 0.0005, "threshold": 500.0, "children": []}]}]}, 3000.0) 返回 4.0。两层走：root 这一层 T1 合格，贡献 0.001 · 3000 = 3.0；剩余降为 2000；进入 T1，T1a 合格，贡献 0.0005 · 2000 = 1.0；总 4.0。
solution({"tier_name": "root", "rate": 0.0, "threshold": 0.0, "children": [{"tier_name": "T1", "rate": 0.001, "threshold": 1000.0, "children": []}, {"tier_name": "T2", "rate": 0.002, "threshold": 5000.0, "children": []}]}, 500.0) 返回 0.0。没有合格档：V=500 低于两个 threshold，递归在 root 这一层立即终止，零返利。
实务场景
阶梯式返利叠加是 prime broker / 交易所费率表的标准结构：月度成交量打到 $X 解锁「白银」档，白银档内再打到 $5X 解锁「白银 Plus」子档，白银 Plus 内再打到 $25X 解锁「黄金」档，依此类推。把它建模成树是天然的——不同的父档可以分叉成不同的子档结构（比如期货量黄金档的子档福利与现货黄金档完全不同）。客户月底以累计量 V 收尾时，你就在这棵树上走一遍来算出实际返利。「合格者中选 threshold 最大」这条规则正好对应费率表的标准语义：永远按你能合格的最高档位计费，不会回去按已经越过的低档计。同样的形态（贪心下行 + 逐层计费 + 剩余量往下传）在累进所得税档位、忠诚度积分阶梯、分层保险免赔额等场景里都会出现——任何一种「分层费率表 + 单个汇总输入」的评估都是它。
约束条件
- 每个节点是 dict：`{"tier_name": str, "rate": float, "threshold": float, "children": list[node]}`。
- 根节点按规约 `threshold = 0` 且 `rate = 0`——它是入口哨兵节点，本身从不贡献返利。只有它的后代会贡献。
- 树深度 ≤ 10；每个节点的分叉数 ≤ 5。
- `volume ∈ [0, 1e9]`；`rate ∈ [0, 1]`；`threshold ∈ [0, 1e9]`。
- 每层选档规则：在 `children` 中合格（即 `threshold ≤ remaining_volume`）的集合里，挑 `threshold` **最大**的那个；若合格集为空，则终止。
- 终止条件：`remaining_volume` 降到 0 时也终止递归（不再下钻）。
- 返回值的浮点容差：rel_tol = 1e-9, abs_tol = 1e-12。
样例
Case 1 · root with no children: terminate immediately
输入: [{"tier_name":"root","rate":0,"threshold":0,"children":[]},100000]
期望: 0
根节点没有任何子层级（rebate 表为空）。算法从 root 出发扫描 children 找最大合格 threshold，children 为空集合，立刻终止，返回 0。这道题确认你处理了 children 为空的边界，而不是误以为 root 自己也要把 rate·V 加进去——按规约，root.rate=0 仅作为入口约定，本身从不贡献返利。
Case 2 · single tier, volume above threshold
输入: [{"tier_name":"root","rate":0,"threshold":0,"children":[{"tier_name":"T1","rate":0.001,"threshold":1000,"children":[]}]},5000]
期望: 5
一层 rebate 表，唯一档位 T1：rate=0.001, threshold=1000。V=5000 ≥ 1000，T1 合格 → 返利 = 0.001·5000 = 5.0。然后递归到 T1，剩余量 5000−1000=4000，T1.children 为空 → 立刻终止。总返利 5.0。这是单层走一步的最简正例。
Case 3 · single tier, volume below threshold: no qualifier
输入: [{"tier_name":"root","rate":0,"threshold":0,"children":[{"tier_name":"T1","rate":0.001,"threshold":1000,"children":[]}]},500]
期望: 0
V=500 不到 T1 的 threshold=1000，没有合格档位 → 直接终止，返利为 0。这道题确认你过滤掉 threshold > remaining_volume 的子节点，不会强行套用 rate。
Case 4 · threshold exactly matches volume: boundary qualifies
输入: [{"tier_name":"root","rate":0,"threshold":0,"children":[{"tier_name":"T1","rate":0.002,"threshold":1000,"children":[{"tier_name":"T2","rate":0.005,"threshold":100,"children":[]}]}]},1000]
期望: 2
边界相等：V=1000 等于 T1.threshold=1000，按 `threshold ≤ V` 的规则 T1 仍然合格。返利 = 0.002·1000 = 2.0。递归后 remaining = 1000−1000 = 0，依规约 volume drops to zero 时立即终止 → 不再进入 T2，即使 T2 的 threshold=100 在「上一层 V」下原本会合格。这道题考你两件事：相等是否算合格（是），以及 V=0 是否要继续递归（不要）。
Case 5 · multiple siblings: pick max qualifying threshold
输入: [{"tier_name":"root","rate":0,"threshold":0,"children":[{"tier_name":"Bronze","rate":0.001,"threshold":100,"children":[]},{"tier_name":"Silver","rate":0.0015,"threshold":500,"children":[]},{"tier_name":"Gold","rate":0.002,"threshold":2000,"children":[]}]},1500]
期望: 2.25
三档：Bronze(100)/Silver(500)/Gold(2000)。V=1500 时合格集为 {Bronze, Silver}（Gold 的 2000 > 1500 被排除）。规则是从合格集里选 threshold 最大者 → Silver 中标，rate=0.0015。返利 = 0.0015·1500 = 2.25。这道题验证你 (a) 排除掉 threshold > V 的 Gold，(b) 在剩下的里挑 max-threshold，而不是 max-rate 或第一个合格的。
Case 6 · two-level cumulative walk
输入: [{"tier_name":"root","rate":0,"threshold":0,"children":[{"tier_name":"T1","rate":0.001,"threshold":1000,"children":[{"tier_name":"T1a","rate":0.0005,"threshold":500,"children":[]}]}]},3000]
期望: 4
两层：T1(rate=0.001, thr=1000) → T1a(rate=0.0005, thr=500)。V=3000：T1 合格 → 返利 0.001·3000 = 3.0；剩 3000−1000 = 2000。进入 T1，扫子档：T1a 合格 → 返利 0.0005·2000 = 1.0；剩 2000−500 = 1500。T1a 无子档终止。总 = 3.0 + 1.0 = 4.0。注意每层的「rate · remaining_volume」都是当前剩余量，不是原始 V。
Case 7 · three-level deep walk: rebate compounds down
输入: [{"tier_name":"root","rate":0,"threshold":0,"children":[{"tier_name":"A","rate":0.002,"threshold":10000,"children":[{"tier_name":"B","rate":0.001,"threshold":5000,"children":[{"tier_name":"C","rate":0.0005,"threshold":2000,"children":[]}]}]}]},20000]
期望: 52.5
三层链：A(0.002, thr=10000) → B(0.001, thr=5000) → C(0.0005, thr=2000)，V=20000。A 合格 → 0.002·20000 = 40.0，剩 10000。B 合格 → 0.001·10000 = 10.0，剩 5000。C 合格 → 0.0005·5000 = 2.5，剩 3000。C 无子终止。总 = 40 + 10 + 2.5 = 52.5。这道题考你递归是否真把 remaining_volume 一层层往下传，而不是错用 V 或上一层的 remaining。
Case 8 · branching at level-2: pick max-threshold among multiple qualifiers
输入: [{"tier_name":"root","rate":0,"threshold":0,"children":[{"tier_name":"A","rate":0.002,"threshold":1000,"children":[{"tier_name":"B1","rate":0.001,"threshold":500,"children":[]},{"tier_name":"B2","rate":0.0008,"threshold":2000,"children":[]},{"tier_name":"B3","rate":0.0012,"threshold":3000,"children":[]}]}]},4000]
期望: 11.6
level-1 只有 A：返利 = 0.002·4000 = 8.0，剩 3000。level-2 有 B1/B2/B3 三个候选，threshold 分别 500/2000/3000，全都 ≤ 3000 → 全部合格。按 max-threshold 规则选 B3（thr=3000，rate=0.0012）。返利 = 0.0012·3000 = 3.6。剩 0 → 终止。总 = 8.0 + 3.6 = 11.6。注意 B3 的 rate（0.0012）并不是三个里最大的（B1=0.001、B3=0.0012、B2=0.0008，B3 最大确实，但若把 B2 改成 0.005 也仍要选 B3）——选档准则是 threshold 最大，与 rate 无关。
最近提交
还没有提交记录。
编码区
实现 solution(...)。本地运行当前支持 Python 可见样例；服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出；点击「提交评测」会进入隐藏测试。
Case 1 · root with no children: terminate immediately
输入: [{"tier_name":"root","rate":0,"threshold":0,"children":[]},100000]
期望: 0
根节点没有任何子层级（rebate 表为空）。算法从 root 出发扫描 children 找最大合格 threshold，children 为空集合，立刻终止，返回 0。这道题确认你处理了 children 为空的边界，而不是误以为 root 自己也要把 rate·V 加进去——按规约，root.rate=0 仅作为入口约定，本身从不贡献返利。
Case 2 · single tier, volume above threshold
输入: [{"tier_name":"root","rate":0,"threshold":0,"children":[{"tier_name":"T1","rate":0.001,"threshold":1000,"children":[]}]},5000]
期望: 5
一层 rebate 表，唯一档位 T1：rate=0.001, threshold=1000。V=5000 ≥ 1000，T1 合格 → 返利 = 0.001·5000 = 5.0。然后递归到 T1，剩余量 5000−1000=4000，T1.children 为空 → 立刻终止。总返利 5.0。这是单层走一步的最简正例。
Case 3 · single tier, volume below threshold: no qualifier
输入: [{"tier_name":"root","rate":0,"threshold":0,"children":[{"tier_name":"T1","rate":0.001,"threshold":1000,"children":[]}]},500]
期望: 0
V=500 不到 T1 的 threshold=1000，没有合格档位 → 直接终止，返利为 0。这道题确认你过滤掉 threshold > remaining_volume 的子节点，不会强行套用 rate。
Case 4 · threshold exactly matches volume: boundary qualifies
输入: [{"tier_name":"root","rate":0,"threshold":0,"children":[{"tier_name":"T1","rate":0.002,"threshold":1000,"children":[{"tier_name":"T2","rate":0.005,"threshold":100,"children":[]}]}]},1000]
期望: 2
边界相等：V=1000 等于 T1.threshold=1000，按 `threshold ≤ V` 的规则 T1 仍然合格。返利 = 0.002·1000 = 2.0。递归后 remaining = 1000−1000 = 0，依规约 volume drops to zero 时立即终止 → 不再进入 T2，即使 T2 的 threshold=100 在「上一层 V」下原本会合格。这道题考你两件事：相等是否算合格（是），以及 V=0 是否要继续递归（不要）。
Case 5 · multiple siblings: pick max qualifying threshold
输入: [{"tier_name":"root","rate":0,"threshold":0,"children":[{"tier_name":"Bronze","rate":0.001,"threshold":100,"children":[]},{"tier_name":"Silver","rate":0.0015,"threshold":500,"children":[]},{"tier_name":"Gold","rate":0.002,"threshold":2000,"children":[]}]},1500]
期望: 2.25
三档：Bronze(100)/Silver(500)/Gold(2000)。V=1500 时合格集为 {Bronze, Silver}（Gold 的 2000 > 1500 被排除）。规则是从合格集里选 threshold 最大者 → Silver 中标，rate=0.0015。返利 = 0.0015·1500 = 2.25。这道题验证你 (a) 排除掉 threshold > V 的 Gold，(b) 在剩下的里挑 max-threshold，而不是 max-rate 或第一个合格的。
Case 6 · two-level cumulative walk
输入: [{"tier_name":"root","rate":0,"threshold":0,"children":[{"tier_name":"T1","rate":0.001,"threshold":1000,"children":[{"tier_name":"T1a","rate":0.0005,"threshold":500,"children":[]}]}]},3000]
期望: 4
两层：T1(rate=0.001, thr=1000) → T1a(rate=0.0005, thr=500)。V=3000：T1 合格 → 返利 0.001·3000 = 3.0；剩 3000−1000 = 2000。进入 T1，扫子档：T1a 合格 → 返利 0.0005·2000 = 1.0；剩 2000−500 = 1500。T1a 无子档终止。总 = 3.0 + 1.0 = 4.0。注意每层的「rate · remaining_volume」都是当前剩余量，不是原始 V。
Case 7 · three-level deep walk: rebate compounds down
输入: [{"tier_name":"root","rate":0,"threshold":0,"children":[{"tier_name":"A","rate":0.002,"threshold":10000,"children":[{"tier_name":"B","rate":0.001,"threshold":5000,"children":[{"tier_name":"C","rate":0.0005,"threshold":2000,"children":[]}]}]}]},20000]
期望: 52.5
三层链：A(0.002, thr=10000) → B(0.001, thr=5000) → C(0.0005, thr=2000)，V=20000。A 合格 → 0.002·20000 = 40.0，剩 10000。B 合格 → 0.001·10000 = 10.0，剩 5000。C 合格 → 0.0005·5000 = 2.5，剩 3000。C 无子终止。总 = 40 + 10 + 2.5 = 52.5。这道题考你递归是否真把 remaining_volume 一层层往下传，而不是错用 V 或上一层的 remaining。
Case 8 · branching at level-2: pick max-threshold among multiple qualifiers
输入: [{"tier_name":"root","rate":0,"threshold":0,"children":[{"tier_name":"A","rate":0.002,"threshold":1000,"children":[{"tier_name":"B1","rate":0.001,"threshold":500,"children":[]},{"tier_name":"B2","rate":0.0008,"threshold":2000,"children":[]},{"tier_name":"B3","rate":0.0012,"threshold":3000,"children":[]}]}]},4000]
期望: 11.6
level-1 只有 A：返利 = 0.002·4000 = 8.0，剩 3000。level-2 有 B1/B2/B3 三个候选，threshold 分别 500/2000/3000，全都 ≤ 3000 → 全部合格。按 max-threshold 规则选 B3（thr=3000，rate=0.0012）。返利 = 0.0012·3000 = 3.6。剩 0 → 终止。总 = 8.0 + 3.6 = 11.6。注意 B3 的 rate（0.0012）并不是三个里最大的（B1=0.001、B3=0.0012、B2=0.0008，B3 最大确实，但若把 B2 改成 0.005 也仍要选 B3）——选档准则是 threshold 最大，与 rate 无关。