通用二叉树上的逆向归纳

一棵情景树沿时间向前展开：每个内部节点上世界先实现一个状态，立刻支付 value_at_node，然后以概率 prob_up 进入 up_child、以概率 1 − prob_up 进入 down_child；未来子树产生的现金流要再乘一个每步折扣因子 discount。叶子节点上世界停下，实现的现金流就是 value。把这棵树折叠成一个标量——「以现在为时点的期望值」——的标准做法叫逆向归纳（backward induction）：从叶子算起、一层层往根回卷。

请实现 solution(tree: dict, discount: float) -> float，返回 tree 在每步折扣因子 discount 下的根节点期望值。tree 用嵌套字典编码：

• 叶子：{"is_leaf": True, "value": <float>}
• 内部节点：{"is_leaf": False, "value_at_node": <float>, "prob_up": <float>, "up_child": <subtree>, "down_child": <subtree>}

递推关系是：

EV(leaf)     = leaf["value"]
EV(internal) = value_at_node + discount · (prob_up · EV(up_child) + (1 − prob_up) · EV(down_child))

校验：使用前请检查 discount ∈ [0, 1] 与每个 prob_up ∈ [0, 1]，超界请抛 ValueError 并附清晰错误信息。discount = 0（短视）、discount = 1（不衰减）都是合法的；prob_up = 0 与 prob_up = 1（确定性分支）也合法。

示例

solution({"is_leaf": True, "value": 42.5}, 0.95) 返回 42.5。根本身就是叶子，折扣因子根本用不上——没有未来子树要折现。

solution({"is_leaf": False, "value_at_node": 0.0, "prob_up": 0.6, "up_child": {"is_leaf": True, "value": 100.0}, "down_child": {"is_leaf": True, "value": -40.0}}, 0.95) 返回 41.8。深度 1 的树，两个孩子都是叶子：0 + 0.95 · (0.6 · 100 + 0.4 · (−40)) = 0.95 · 44 = 41.8。

solution({"is_leaf": False, "value_at_node": 5.0, "prob_up": 0.7, "up_child": {"is_leaf": True, "value": 50.0}, "down_child": {"is_leaf": False, "value_at_node": 1.0, "prob_up": 0.3, "up_child": {"is_leaf": True, "value": 10.0}, "down_child": {"is_leaf": True, "value": -20.0}}}, 0.9) 大约返回 34.097。深度-2 的非对称树：上行子树是叶子，下行子树是另一个内部节点带自己的两片叶子——这种形状重组型格点表达不了。

实战背景

通用递归二叉树上的逆向归纳，远不止用在衍生品定价上——只要你手上有一棵带阶段支付与概率转移的离散决策树或情景树，都用得上：研究侧的情景分析（「若事件 A 发生，则事件 B 有 30% 概率发生，那时候……」）、策略博弈树的局面值评估、显式分支状态空间上的动态规划、结构化不确定性下的期望效用计算。本题的树形是任意的（而非重组型格点），所以正是当一个节点的两个子节点拥有不同后续可能性时——也就是格点捷径失效时——你应当抓起来用的工具。把这个原语写好之后，换掉叶子基底情况（改成返回 payoff）、换掉合并算子（把折扣期望值换成 max 得到最优策略树，换成风险加权和得到最坏情景聚合），就分别得到决策树 EV、博弈树 minimax、风险调整情景汇总——同一个递归骨架可以撑起这几类不同任务。