情景树上每节点的条件期望叶节点收益
Per-Node Conditional Expected Leaf Payoff on a Scenario Tree
开始编码输入是一棵以三个平行层序数组形式给出的情景树。parent_idx[i] 是节点 i 的父节点 index（parent_idx[0] = -1 标记根）；对 i >= 1，parent_idx[i] 在 [0, i-1] 区间，因此任意父节点必出现在其所有子节点之前。node_prob[i] 是从父节点到达节点 i 的条件概率（根的 node_prob[0] 约定为 1.0，且不进入递推）。leaf_payoff[i] 是节点 i 在其为叶时的收益，否则按规约为 0.0。节点为叶当且仅当没有其它节点把它列为父亲（多个节点可共享同一父——一般树，不一定是二叉树）。
实现 solution(parent_idx: list[int], node_prob: list[float], leaf_payoff: list[float]) -> list[float]，返回长度为 N 的 float 列表，其中 output[v] 是把 v 视作局部子树根时，其子树的每节点条件期望叶节点收益。递推为
承重的细节：v 自身 incoming 的 node_prob[v] 不进入 output[v]——在节点 v 处我们已经条件于 v 已被到达，对每个子分支乘以的是 node_prob[c]（子节点给定父节点的条件概率）。根处的结果即整棵树的无条件期望叶收益；任意内部节点处的结果即该节点子树（视该节点为局部根）的期望叶收益。
一次后序 DFS（或等价地：利用层序属性用 for i in range(N-1, -1, -1) 倒序扫描——任意子节点 index 严格大于父节点，故每次访问父节点时其子节点都已 finalise）即可在 O(N) 时间、O(N) 空间内算出所有 N 个值。倒序扫描还规避了 Python 默认 1000 层的递归上限——N = 4000 的链状树上递归会直接爆栈。
例
solution(
parent_idx = [-1, 0, 0, 1, 1, 2],
node_prob = [1.0, 0.6, 0.4, 0.5, 0.5, 1.0],
leaf_payoff = [0.0, 0.0, 0.0, 100.0, -20.0, 50.0]
)返回 [44.0, 40.0, 50.0, 100.0, -20.0, 50.0]。节点 3、4、5 都是叶（没有任何节点把它们列为父），故 output[3] = 100.0、output[4] = -20.0、output[5] = 50.0。节点 1 有两个孩子 3 和 4：output[1] = 0.5 * 100 + 0.5 * (-20) = 40.0。节点 2 只有一个孩子 5：output[2] = 1.0 * 50 = 50.0。根有两个孩子 1 和 2：output[0] = 0.6 * 40 + 0.4 * 50 = 44.0。注意计算 output[1] 自身时不乘 node_prob[1] = 0.6——这个因子只在父节点（节点 0）汇总子节点贡献时才出现。每节点条件化是承重的关键：在节点 1 处给出的是「给定节点 1 已被到达条件下」的期望叶收益（40.0），而不是节点 1 对根的联合贡献（0.6 * 40.0 = 24.0，这是父节点递推自然取到的量）。
朴素的「对每个节点单独枚举其子树内所有叶」做法在最差情形下是 O(N^2)（平衡树是 O(N log N) 的总聚合工作量；但链状结构会触满二次界）。后序 DFS 递推则是 O(N)：每条边只贡献一次——子节点的 output 算一次后被父节点的聚合复用一次。
实践背景
多期情景树上的「每节点期望收益」聚合是 backward-induction 类定价引擎的核心算子：在每个内部节点上，交易桌想要的是给定到达该节点的条件期望终端收益，而不仅仅是根节点的总期望，这样才能在每个情景节点处比较「现在执行 vs 继续等待」「现在再平衡 vs 保持仓位」。同样的每节点聚合还会喂给嵌套 VaR 贡献（每棵子树的期望短缺）、real-options 决策树（每个决策节点上的期望收益）以及任何需要逐期检视中间阶段期望（而不仅是最终期望）的情景行走流程。这条递推是最干净的反向归纳——一次后序 DFS、O(N)——且在一般树（非二叉）上无需任何形态变化即可工作，这恰好是生产用情景生成器在每阶段允许超过两种 outcome 时给出的形态。
约束条件
- 1 <= N <= 4000，其中 N == len(parent_idx) == len(node_prob) == len(leaf_payoff)。parent_idx[0] = -1；i >= 1 时 parent_idx[i] 在 [0, i-1] 区间（层序属性）。
- 0.0 <= node_prob[i] <= 1.0；node_prob[0] 是根节点的 incoming 概率，约定为 1.0——不进入任何递推。
- leaf_payoff[i] 为带符号 float，abs(leaf_payoff[i]) <= 1e6。按规约非叶节点的 leaf_payoff[i] 为 0.0；递推对非叶节点也不会用到这一项。节点是叶当且仅当没有其它节点把它列为父亲（多个节点可共享同一父节点——一般树，不一定是二叉树）。
- 返回一个长度为 N 的 Python float 列表——output[v] 是 v 子树的每节点条件期望叶节点收益。比对绝对容差 1e-9。单根无子（根本身是叶）时：返回 [leaf_payoff[0]]。
- 若某个内部子树的 node_prob[i] = 0，意味着该子树对其父节点的贡献为零（确定性剪枝）。公式不做任何归一化——若某节点子节点的 node_prob 之和不为 1，直接按给定概率计算。
样例
Case 1 · statement-example: small tree, root=44.0
输入: [[-1,0,0,1,1,2],[1,0.6,0.4,0.5,0.5,1],[0,0,0,100,-20,50]]
期望: [44,40,50,100,-20,50]
节点3,4,5 是叶；output[1]=0.5*100+0.5*(-20)=40；output[2]=1.0*50=50；output[0]=0.6*40+0.4*50=44。
Case 2 · typical: balanced binary tree all-positive
输入: [[-1,0,0,1,1,2,2],[1,0.5,0.5,0.7,0.3,0.4,0.6],[0,0,0,10,20,30,40]]
期望: [24.5,13,36,10,20,30,40]
叶节点 3,4,5,6；output[1]=0.7*10+0.3*20=13；output[2]=0.4*30+0.6*40=36；output[0]=0.5*13+0.5*36=24.5。
Case 3 · typical: mixed-sign payoffs at leaves
输入: [[-1,0,0,0,1,1,2,3],[1,0.5,0.3,0.2,0.5,0.5,1,1],[0,0,0,0,5,-5,100,-200]]
期望: [-10,0,100,-200,5,-5,100,-200]
三叉根。output[1]=0.5*5+0.5*(-5)=0；output[2]=1*100=100；output[3]=1*(-200)=-200；output[0]=0.5*0+0.3*100+0.2*(-200)=-10。
Case 4 · typical: probs sum to less than 1 at internal node (no normalisation)
输入: [[-1,0,0,1,1],[1,0.3,0.4,0.5,0.5],[0,0,50,10,30]]
期望: [26,20,50,10,30]
节点 2,3,4 是叶。output[1]=0.5*10+0.5*30=20；output[2]=50；output[0]=0.3*20+0.4*50=26（公式不做归一化）。
Case 5 · typical: asymmetric tree (left chain, right leaf)
输入: [[-1,0,0,1,3],[1,0.6,0.4,1,1],[0,0,100,0,-50]]
期望: [10,-50,100,-50,-50]
节点 4 通过 1->3->4 链；output[4]=-50；output[3]=1*(-50)=-50；output[1]=1*(-50)=-50；output[2]=100；output[0]=0.6*(-50)+0.4*100=10。
Case 6 · typical: all leaf_payoff zero -> all-zero output
输入: [[-1,0,0,1,1,2],[1,0.5,0.5,0.5,0.5,1],[0,0,0,0,0,0]]
期望: [0,0,0,0,0,0]
所有叶 payoff 为 0，故所有节点 output 均为 0。
Case 7 · boundary: N=1, root is leaf
输入: [[-1],[1],[42.5]]
期望: [42.5]
单节点 N=1，根本身是叶；output=[42.5]。
Case 8 · boundary: N=1, root leaf payoff 0.0
输入: [[-1],[1],[0]]
期望: [0]
单节点 N=1，叶 payoff 为 0；output=[0.0]。
Case 9 · boundary: N=2, root + one leaf child
输入: [[-1,0],[1,0.7],[0,100]]
期望: [70,100]
节点 1 是叶；output[1]=100；output[0]=0.7*100=70。
Case 10 · boundary: node_prob=0 deterministically prunes subtree
输入: [[-1,0,0,1,1],[1,0,1,0.5,0.5],[0,0,100,999,-999]]
期望: [100,0,100,999,-999]
节点 1 的 node_prob=0；output[1]=0.5*999+0.5*(-999)=0；乘 node_prob[1]=0 后对根贡献 0；output[0]=0+1*100=100。
Case 11 · boundary: deterministic chain probability 1.0
输入: [[-1,0,1,2,3],[1,1,1,1,1],[0,0,0,0,77.5]]
期望: [77.5,77.5,77.5,77.5,77.5]
5 节点确定性链；每个 output[v]=77.5 (从该节点出发到达叶概率 1)。
Case 12 · boundary: prob clamped to 1.0 at each child (max value)
输入: [[-1,0,0],[1,1,1],[0,50,30]]
期望: [80,50,30]
两个孩子 prob 都为 1（合法但概率不归一化）；output[0]=1*50+1*30=80。
Case 13 · boundary: all-negative payoffs
输入: [[-1,0,0,0],[1,0.25,0.25,0.5],[0,-100,-200,-50]]
期望: [-100,-100,-200,-50]
三叶；output[0]=0.25*(-100)+0.25*(-200)+0.5*(-50)=-25-50-25=-100。
Case 14 · boundary: max-magnitude leaf payoff 1e6
输入: [[-1,0,0],[1,0.5,0.5],[0,1000000,-1000000]]
期望: [0,1000000,-1000000]
极端 magnitude；output[0]=0.5*1e6+0.5*(-1e6)=0。
Case 15 · boundary: star tree, 5 leaves under root
输入: [[-1,0,0,0,0,0],[1,0.1,0.2,0.3,0.2,0.2],[0,10,20,30,40,50]]
期望: [32,10,20,30,40,50]
星形树；output[0]=0.1*10+0.2*20+0.3*30+0.2*40+0.2*50=1+4+9+8+10=32。
Case 16 · boundary: chain N=10 with prob 0.9 each step
输入: [[-1,0,1,2,3,4,5,6,7,8],[1,0.9,0.9,0.9,0.9,0.9,0.9,0.9,0.9,0.9],[0,0,0,0,0,0,0,0,0,100]]
期望: [38.742048900000015,43.04672100000001,47.829690000000014,53.144100000000016,59.049000000000014,65.61000000000001,72.9,81,90,100]
10 节点链；output[9]=100；output[i]=0.9^(9-i)*100。
Case 17 · boundary: probs sum > 1.0 (no normalisation per spec)
输入: [[-1,0,0],[1,0.7,0.7],[0,10,20]]
期望: [21,10,20]
孩子概率和 > 1，公式不归一化；output[0]=0.7*10+0.7*20=21。
最近提交
还没有提交记录。
编码区
实现 solution(...)。本地运行当前支持 Python 可见样例；服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出；点击「提交评测」会进入隐藏测试。
Case 1 · statement-example: small tree, root=44.0
输入: [[-1,0,0,1,1,2],[1,0.6,0.4,0.5,0.5,1],[0,0,0,100,-20,50]]
期望: [44,40,50,100,-20,50]
节点3,4,5 是叶；output[1]=0.5*100+0.5*(-20)=40；output[2]=1.0*50=50；output[0]=0.6*40+0.4*50=44。
Case 2 · typical: balanced binary tree all-positive
输入: [[-1,0,0,1,1,2,2],[1,0.5,0.5,0.7,0.3,0.4,0.6],[0,0,0,10,20,30,40]]
期望: [24.5,13,36,10,20,30,40]
叶节点 3,4,5,6；output[1]=0.7*10+0.3*20=13；output[2]=0.4*30+0.6*40=36；output[0]=0.5*13+0.5*36=24.5。
Case 3 · typical: mixed-sign payoffs at leaves
输入: [[-1,0,0,0,1,1,2,3],[1,0.5,0.3,0.2,0.5,0.5,1,1],[0,0,0,0,5,-5,100,-200]]
期望: [-10,0,100,-200,5,-5,100,-200]
三叉根。output[1]=0.5*5+0.5*(-5)=0；output[2]=1*100=100；output[3]=1*(-200)=-200；output[0]=0.5*0+0.3*100+0.2*(-200)=-10。
Case 4 · typical: probs sum to less than 1 at internal node (no normalisation)
输入: [[-1,0,0,1,1],[1,0.3,0.4,0.5,0.5],[0,0,50,10,30]]
期望: [26,20,50,10,30]
节点 2,3,4 是叶。output[1]=0.5*10+0.5*30=20；output[2]=50；output[0]=0.3*20+0.4*50=26（公式不做归一化）。
Case 5 · typical: asymmetric tree (left chain, right leaf)
输入: [[-1,0,0,1,3],[1,0.6,0.4,1,1],[0,0,100,0,-50]]
期望: [10,-50,100,-50,-50]
节点 4 通过 1->3->4 链；output[4]=-50；output[3]=1*(-50)=-50；output[1]=1*(-50)=-50；output[2]=100；output[0]=0.6*(-50)+0.4*100=10。
Case 6 · typical: all leaf_payoff zero -> all-zero output
输入: [[-1,0,0,1,1,2],[1,0.5,0.5,0.5,0.5,1],[0,0,0,0,0,0]]
期望: [0,0,0,0,0,0]
所有叶 payoff 为 0，故所有节点 output 均为 0。
Case 7 · boundary: N=1, root is leaf
输入: [[-1],[1],[42.5]]
期望: [42.5]
单节点 N=1，根本身是叶；output=[42.5]。
Case 8 · boundary: N=1, root leaf payoff 0.0
输入: [[-1],[1],[0]]
期望: [0]
单节点 N=1，叶 payoff 为 0；output=[0.0]。
Case 9 · boundary: N=2, root + one leaf child
输入: [[-1,0],[1,0.7],[0,100]]
期望: [70,100]
节点 1 是叶；output[1]=100；output[0]=0.7*100=70。
Case 10 · boundary: node_prob=0 deterministically prunes subtree
输入: [[-1,0,0,1,1],[1,0,1,0.5,0.5],[0,0,100,999,-999]]
期望: [100,0,100,999,-999]
节点 1 的 node_prob=0；output[1]=0.5*999+0.5*(-999)=0；乘 node_prob[1]=0 后对根贡献 0；output[0]=0+1*100=100。
Case 11 · boundary: deterministic chain probability 1.0
输入: [[-1,0,1,2,3],[1,1,1,1,1],[0,0,0,0,77.5]]
期望: [77.5,77.5,77.5,77.5,77.5]
5 节点确定性链；每个 output[v]=77.5 (从该节点出发到达叶概率 1)。
Case 12 · boundary: prob clamped to 1.0 at each child (max value)
输入: [[-1,0,0],[1,1,1],[0,50,30]]
期望: [80,50,30]
两个孩子 prob 都为 1（合法但概率不归一化）；output[0]=1*50+1*30=80。
Case 13 · boundary: all-negative payoffs
输入: [[-1,0,0,0],[1,0.25,0.25,0.5],[0,-100,-200,-50]]
期望: [-100,-100,-200,-50]
三叶；output[0]=0.25*(-100)+0.25*(-200)+0.5*(-50)=-25-50-25=-100。
Case 14 · boundary: max-magnitude leaf payoff 1e6
输入: [[-1,0,0],[1,0.5,0.5],[0,1000000,-1000000]]
期望: [0,1000000,-1000000]
极端 magnitude；output[0]=0.5*1e6+0.5*(-1e6)=0。
Case 15 · boundary: star tree, 5 leaves under root
输入: [[-1,0,0,0,0,0],[1,0.1,0.2,0.3,0.2,0.2],[0,10,20,30,40,50]]
期望: [32,10,20,30,40,50]
星形树；output[0]=0.1*10+0.2*20+0.3*30+0.2*40+0.2*50=1+4+9+8+10=32。
Case 16 · boundary: chain N=10 with prob 0.9 each step
输入: [[-1,0,1,2,3,4,5,6,7,8],[1,0.9,0.9,0.9,0.9,0.9,0.9,0.9,0.9,0.9],[0,0,0,0,0,0,0,0,0,100]]
期望: [38.742048900000015,43.04672100000001,47.829690000000014,53.144100000000016,59.049000000000014,65.61000000000001,72.9,81,90,100]
10 节点链；output[9]=100；output[i]=0.9^(9-i)*100。
Case 17 · boundary: probs sum > 1.0 (no normalisation per spec)
输入: [[-1,0,0],[1,0.7,0.7],[0,10,20]]
期望: [21,10,20]
孩子概率和 > 1，公式不归一化；output[0]=0.7*10+0.7*20=21。