适用范围
对于一些只有状态上的值不同而转移方程完全相同的 dp 可以考虑使用这个 trick。
一般用线段树合并维护,当前点 (x) 的线段树的叶子节点下标 (y) 的位置的权值,是第 (y) 次 dp 到 (x) 这里的权值。
例题
[NOIp 2018] 保卫王国
转移方程为：
[egin{aligned}
f_{x, 0} &= sum_{y in mathrm{son}_x} f_{y, 1}\
f_{x, 1} &= p_x + sum_{y in mathrm{son}_x} f_{y, 1}
end{aligned}
]
用线段树合并维护 (m) 次询问，那么一个 a x b y 的询问相当于线段树上的单点修改，可以用矩阵维护。
在向父亲合并时需要乘上以下矩阵 (egin{bmatrix} infty & 0\0 & 0 end{bmatrix}) 以方便合并：
[egin{bmatrix} f_0 & f_1 end{bmatrix} imes egin{bmatrix} infty & 0\0 & 0 end{bmatrix} = egin{bmatrix} f_1 & min(f_0, f_1) end{bmatrix}
]
代码要比正常的动态 dp 短很多。code
[九省联考 2018] 秘密袭击
前面的推导部分不再赘述。
用生成函数的方式表示出转移方程。
[F_{i, j} = x ^ {[v_i geq j]} prod_{p = 1}^{|s|} (F_{s_p, j} + 1)
]
先枚举一个数字 (p)，设 (f_{i, y}) 表示 (F_{i, y}(x)) 这个生成函数在 (x = p) 时候的点值，为了方便枚举答案，设 (g_{i, y}) 表示 (f_{i, y}) 的子树和。
用线段树合并维护 (f) 和 (g)，于是需要支持这两个操作：
- (f) 整体 (+ 1) 和整体乘上一个数。
- 将 (f) 加到 (g) 上。
考虑定义一个变换 ((a, b, c, d)) 使得 ((f, g) o (af + b, cf + d + g))，那么两个变换 ((a_1, b_1, c_1, d_1)) 和 ((a_2, b_2, c_2, d_2)) 合并会变成 ((a_1a_2, a_2b_1 + b_2, c1 + c_2a_1, c_2b_1 + d_1 + d_2))，这样就可以很好维护了，只需要最后再插值回来即可。
这个标记应该也可以用矩阵维护。code