树上消元

· · 个人记录

如果一个 DP 可以表示为树，有时候会遇到这样的转移方程：

f_i=af_{fa}+\sum_{j\in i.son} b_jf_j+c.

状态有了后效性，这个时候不能递推而是要解方程组。

但是大部分时候高斯消元会 TLE，所以引入树上消元。尝试把 f_i 表示为 Af_{fa}+B 的形式。

递归分解儿子后，就可以把转移方程转化为

f_i=af_{fa}+\sum b_j(A_2f_i+B_2)+c.

设乘上系数之后就可以转化为

f_i=af_{fa}+A_1f_i+B_1.

的形式。

解得

f_i=\frac a{1-A_1}\times f_{fa}+\frac{B_1}{1-A_1}.

所以 A=\frac a{1-A_1}，B=\frac{B_1}{1-A_1}.

若题目未给出边界条件，则当 i 超过树的范围时，A=B=0.

时间复杂度为 O(n).