题解：P4719 【模板】动态 DP

动态 dp 主要运用于树上或者区间上的 dp 问题，核心是将本来的转移过程写成矩阵转移的形式，构造矩阵 $g_i$ 以及广义矩阵乘法使得 $f_j \times g_i = f_i$。

然后呢，我们对于这个 $g_i$，通过发掘原题的性质，让它在原做法中乘上若干个 $g$ 变成只乘一个 $g$。换句话说呢就是需要维护一段连续的区间，在这个区间里提前进行转移（可以用线段树维护）。一般树上的做法可以是树链剖分变成 dfs 序再用线段树维护转移矩阵。做法因题目而异。

下面看例题。

不妨先考虑没有修改怎么做，套路的考虑树形 dp，设 $f_{i,0/1}$ 表示 $i$ 节点选不选，那么就有 $f_{i,0}=\sum_{j\in son_i} \max(f_{j,0},f_{j,1})$ 表示儿子选不选随意， $f_{i,1}=a_i+\sum_{j\in son_i} f_{j,0}$ 表示儿子一定不能选。

这个时候我们再引入修改操作，由于每个点的 $f$ 值只与他的子节点的值有关，所以我们发现它只会修改一条链上的 $f$ 值。如果考虑维护链上信息，那么就是需要引入树链剖分了。

但是发现信息不是特别好维护，可以定义一个辅助修改数组 $g_{i,0}=\sum_{j\neq h_i} \max(f_{j,0},f_{j,1})$，$g_{i,1}=a_i + \sum_{j\neq h_i} f_{j,0}$，其中 $h_i$ 表示 $i$ 的重儿子。

那么转移就变成了 $f_{i,0}=\max(f_{h_i,0},f_{h_i,1})+g_{i,0}$，$f_{i,1}=f_{h_i,0}+g_{i,1}$。

发现很符合矩阵的样子是吧，那么可以定义广义矩阵乘法 $c_{i,j}=\max_k a_{i,k}+b_{k,j}$，那么就变成了