动态DP？动态动态规划？
个人理解：动态DP，就是普通DP加修改操作，然后就变成了个毒瘤题。
直接就着例题写吧。
例题
P4719 【模板】"动态 DP"&动态树分治
求树上最大独立集。要求支持修改点权。n<=1e5.
算法原理
首先不带修的最大独立集是一个NOIP题：
\(f[cur][0/1]\) 表示 \(cur\) 选/不选 其子树内（含 \(cur\)）的被选点权值和。
\[f[cur][0]= \sum max(f[to][0], f[to][1]) \]
\[f[cur][1] = \sum f[to][0] \]
既然要求支持修改，我们可以拿出对付树的利器：树链剖分。将树剖分成重链和轻边。然后 \(f[cur][0/1]\) 含义不变，另设 \(g[cur][0/1]\) 表示不考虑重儿子的 \(f\)。那么有:
\[g[cur][0]= \sum max(g[to][0], g[to][1]) \]
\[g[cur][1] = \sum g[to][0] \]
为了描述方便，规定 \(i + 1\) 为在重链上与 \(i\) 相邻的比 \(i\) 深的那个点。则：
\[f[i][0] = g[i][0] + max(f[i + 1][0], f[i + 1][1]) \]
\[f[i][1] = g[i][1] + f[i + 1][0] \]
然后我们发现这样老是[0][1]不方便，直接用 \(2×1\) 的矩阵来表示 \(f, g\)，这样的话，我们就发现 \(f\) 矩阵可以由与 \(g\) 有关的矩阵递推：
\[\begin{bmatrix} g_{i,0} & g_{i, 0}\\ g_{i, 1} & -\infty\end{bmatrix} × \begin{bmatrix} f_{i+1, 0} \\ f_{i+1, 1} \end{bmatrix}=\begin{bmatrix} f_{i,0} \\ f_{i,1} \end{bmatrix}\]
这样，我们就只用维护每个点的 \(g\) 矩阵，用到 \(f\) 的时候直接拿 \(g\) 矩阵乘一下即可。这个 \(g\) 矩阵是重链上的一堆矩阵，因此我们可以拿线段树维护。
现在考虑修改带来的影响
如果我们修改了某一个点的权值，那么这个点的 \(g\) 矩阵将会改变，不过重链上的其它 \(g\) 矩阵不会改变。但是，重量顶端的父亲的 \(g\) 矩阵会因为重链上的 \(f\) 的改变而改变，因此我们需要修改重链父亲的 \(g\) 矩阵，以及重链父亲所在重链的顶端的父亲的 \(g\) 矩阵...
流程大概是：修改 \(cur\) 的 \(g\) 矩阵，计算 \(top\) 的 \(f\)，（如果 \(cur\) 尚不为树根），cur = fa[top[cur]]，重复。
代码实现
具体实现的时候，我们自然可以严格按照流程的做法来。不过，相比树剖疯狂跳 \(fa[top]\)，LCT的 \(Access\) 函数也可以较为轻松地实现这种操作，并且LCT可以将信息直接维护到点上，避开线段树无比笨拙的修改查询操作，砍掉一个 \(log\)，而且还不用 \(makeroot\)，因此不用 \(pushr,pushdown\)，是为数不多的LCT比树剖好写的题。所以，这题用LCT维护原图子树信息是个不错的选择。
还有一些简化代码的小 trick：
-
一开始可以让所有边都为虚边，直接一遍DFS计算出所有 \(g\) 矩阵。
-
我们保持1为根节点不变；所有矩阵都可以开成 2×2 的矩阵。这是因为我们矩阵初始化全为 -inf，如果真的要拿一个 2×2 的矩阵和 2×1 的矩阵乘，由于 2×1 矩阵的第二列全为 -inf，最终结果的第二列也将是 -inf，并不会影响答案。
-
最终统计答案的时候，可以直接 \(splay(1)\) 然后就拿 1 节点的 \(mul\) 计算答案。本来应该是 1 所在的实链的底端的那个 \(f\) 矩阵乘其它的 \(g\) 矩阵，但是我们发现底端 \(g\) 矩阵的第一列恰好是 \(f\) 矩阵的第一列，因此乘出来的第一列就恰好是答案。
关键代码
略微感受到shadowice大佬考场调bug的感觉了，我还是刚学完ddp,理清思路再写，还写出了五个bug。
int h[N];
matrix val[N], mul[N];
int son[N][2], fa[N];
inline void pushup(int cur) {
mul[cur] = val[cur];
int ls = son[cur][0], rs = son[cur][1];
if (ls) mul[cur] = mul[ls] * mul[cur];
if (rs) mul[cur] = mul[cur] * mul[rs];
}
inline void Access(int cur) {
for (register int p = cur, lst = 0; p; lst = p, p = fa[p]) {
splay(p);//Attention!
if (lst) {
val[p].h[0][0] -= max(mul[lst].h[0][0], mul[lst].h[1][0]);//Attention!!! : mul
val[p].h[1][0] -= mul[lst].h[0][0];//Attention!!! : mul
}
int rs = son[p][1];
if (rs) {
val[p].h[0][0] += max(mul[rs].h[0][0], mul[rs].h[1][0]);//Attention!!!
val[p].h[1][0] += mul[rs].h[0][0];//Attention!!!
}
val[p].h[0][1] = val[p].h[0][0];
son[p][1] = lst;
pushup(p);
}
}
int g[N][2];
void dfs(int cur, int faa) {
g[cur][1] = h[cur]; fa[cur] = faa;
for (register int i = head[cur]; i; i = e[i].nxt) {
int to = e[i].to; if (to == faa) continue;
dfs(to, cur);
g[cur][0] += max(g[to][0], g[to][1]);
g[cur][1] += g[to][0];
}
val[cur].h[0][0] = val[cur].h[0][1] = g[cur][0];
val[cur].h[1][0] = g[cur][1];//Attention!
mul[cur] = val[cur];
}
inline void modify(int cur, int v) {
Access(cur), splay(cur);
// val[cur].h[0][0] += v - h[cur];
// val[cur].h[0][1] = val[cur].h[0][0];
val[cur].h[1][0] += v - h[cur];//Attention!!!
h[cur] = v;//Attention!
pushup(cur);
}
int main() {
dfs(1, 0);
while (m--) {
modify(x, v);
splay(1);
ans = max(mul[1].h[0][0], mul[1].h[1][0]);
}
}