设 $F_u(i,j)$ 表示 $u$ 子树内 $A,B$ 的最优收益达到了 $i,j$ 的方案数，$X_u(i),Y_u(i)$ 表示 $A,B$ 收益不超过 $i$ 的方案数。讨论 $u\in A$ 的转移，$B$ 中对称。我们有 $$ F_u(i,j) = F_l(i,j) X_r(i) + F_r(i,j) X_l(i) $$ 和 $$ \begin{aligned} X_u(i) &= 2 X_l(i) X_r(i) \\ Y_u(i) &= Y_l(i) 2^{|A_r|+|B_r|} k^{2|L_r|} + Y_r(i) 2^{|A_l|+|B_l|} k^{2|L_l|} \end{aligned} $$

如此即可 $\Theta(n^3)$ 解决问题。

首先注意到 $X_u,Y_u$ 分别是多项式。但是 $F_u$ 是二元多项式，这不好。然而，或许与其纳什均衡的背景相关，$F_u(i,j)$ 的两元其实是独立的。有 $$ F_u(i,j) = U_u(i) V_u(j) $$

且可以归纳证明 $$ \begin{aligned} X_u(i) &= 2^{|A_u|} k^{|L_u|} U_u(i) i \\ Y_u(i) &= 2^{|B_u|} k^{|L_u|} V_u(i) i \end{aligned} $$

且可以验证 $u\in A$ 时 $U_u,V_u$ 有递推式 $$ \begin{aligned} U_u(i) &= U_l(i) U_r(i) i \\ V_u(i) &= V_l(i) 2^{|A_r|} k^{|L_r|} + V_r(i) 2^{|A_l|} k^{|L_l|} \end{aligned} $$

从而这样计算点值，最后插出一项点值即可。这样即可 $\Theta(n^2)$。

如果使用 NTT，结合转置原理和链分治也可以做到 $O(n \log^2 n)$。