这个算法的名字好毒瘤的样子。。。Dynamically Dynamical Programming,动态 – 动态规划,简称 DDP。

我们先考虑简单的动态规划。有一个经典问题叫做树上最大权独立集。比如 没有上司的舞会

那么我们可以设 $f_{u,1}$ 为 $u$ 在独立集内的最大收益,$f_{u,0}$ 为 $u$ 不在独立集内的最大收益。转移方程如下:

$$f_{u,1}=\sum_{v\in son}f_{v,0}$$
$$f_{u,1}=\sum_{v\in son}\max (f_{v,0},f_{v,1})$$

现在我们要支持的操作是动态修改某个点的权值,比如 洛谷模板

为了快速维护,我们先对整棵树做一个树剖,然后对每一条重链分别进行 dp。

对于重链上的每个点,先根据轻儿子的 $f$ 维护 $g_{u,1/0}$:

$$g_{u,0}=\sum_{v\in lightson}\max(f_{v,0},f_{v,1})$$

$$g_{u,1}=\sum_{v\in lightson} f_{v,0}$$

对于重链上的点,则有:

$$f_{u,0}=g_{u,0}+\max(f_{heavyson,0},f_{heavyson,1})$$

$$f_{u,1}=g_{u,1}+f_{heavyson,0}$$

这样,树上的问题就转化成了序列上的问题。我们可以对于每条重链维护一颗线段树。修改一个点的值就在这个点所在重链的线段树上修改,最后改变了重链顶端的点的 $f$ 值,进而影响了其父亲的 $g$ 值,反复向上修改,时间复杂度就是 $\Theta(log^2n)$ 的。

问题来了,如何用线段树维护 $f$ 呢。我们重新定义矩阵乘法。对于 $C=A\times B$,有

$$C_{i,j}=\max\limits_{k=1}^{n}(A_{i,k}+B_{k,j})$$

于是,重链上的转移可以写成这样的矩乘

$${\left[ \begin{array}{cc}g_{i,0} &g_{i,0}\\ g_{i,1} &0\end{array} \right ]}\times{\left[ \begin{array}{cc}f_{i+1,0} & f_{i,0}\\ f_{i+1,1} & 0 \end{array} \right ]}={\left[ \begin{array}{cc}f_{i,0}\\ f_{i,1} \end{array} \right ]}$$

重定义以后的矩阵乘法依然满足结合律。我们在线段树上维护矩阵的连乘积,可以实现 $\Theta(8log^2n)$ 的修改操作。

总结一下思路:树剖,维护区间矩阵乘积。修改时从被修改节点所在重链不断向上跳。每次答案就是 $root$ 的 $f$ 值。

伪代码