前言
好消息，CSP-S t4 出 DDP，并且有的人场上为了调 T3 的假算没写。。。
概述
其实是个挺简单的东西，就是如果一道题可以通过 dp 轻松解决，但是题目加上了每次询问修改一些信息的话，每次重新跑 dp 肯定是会寄寄的，所以我们需要一个更加快速的方式。
解决方法很简单，利用矩阵。如果 dp 的转移可以写成一个矩阵，那么我们就可以利用数据结构维护这些矩阵，然后修改的时候就修改这些矩阵，查询的时候直接求矩阵的区间积就可以了。
通常是解决树上问题，所以一般需要和树剖结合。这时候要特别注意树剖的时候的合并。
例题
好嘛，直接上。首先我们可以考虑手推一下 dp 暴力。
我们令 \(f_{i,0/1}\) 表示以 \(i\) 为根的子树中，不选/选根节点的最大权独立集权值。转移显然。
接下来考虑在树上，我们必须利用树剖。所以这样的定义不能够符合树剖的过程。所以我们需要一个和轻重儿子相关的定义。即令 \(g_{i,0}\) 表示以 \(i\) 的所有轻儿子为根的子树中，不取 \(i\) 的所有轻儿子的最大权和，\(g_{i,1}\) 表示以 \(i\) 的所有轻儿子为根的子树中，取或不取 \(i\) 的所有轻儿子的最大权和。
也就是说，我们定义的结果是：（\(A\) 为 \(i\) 的轻儿子集合）
\[g_{i,0}=\sum_{j\in A}f_{j,0}\\ g_{i,1}=\sum_{j\in A}\max(f_{j,0},f_{j,1}) \]则有转移：（\(j\) 为 \(i\) 的重儿子）
\[f_{i,0}=g_{i,1}+\max(f_{j,0},f_{j,1})\\ f_{i,1}=g_{i,0}+a_i+f_{j,0} \]这样一来，\(f\) 的值就只和重链上的前一个节点有关。而 \(g\) 可以在每个点都合并。
现在就可以直接上树剖了，但是矩阵有点麻烦，我们先修改一下定义，令 \(g_{i,0}\) 表示所有轻儿子都不取，并且取上 \(i\) 的最大权值和。即：
\[g_{i,0}=\sum_{j\in A}f_{j,0}+a_i \]那么转移就很简单了，接下来我们构造矩阵。这个矩阵是一个 \(\{\max,+\}\) 矩阵，这样我们就有：
\[\begin{bmatrix}f_{i,0}\\f_{i,1}\end{bmatrix}= \begin{bmatrix}g_{i,1}&g_{i,1}\\g_{i,0}&-\infty\end{bmatrix} \begin{bmatrix}f_{j,0}\\f_{j,1}\end{bmatrix} \]接下来就是树剖的细节了。我们只对每一个重链的链头维护 \(f\)，然后其余的都交给矩阵快速转移。对于叶子有：\(f_{i,0}=0,f_{i,1}=a_i\)，最后乘一手就行了。
然后剖完后建线段树，维护每一个点的转移矩阵，对于一次修改，先修改这个点的矩阵，然后向上跳到链顶，得到新的 \(f\) 值，然后与原 \(f\) 值进行一个比较，得到链顶父亲的 \(g\) 的变化量，然后修改这个点的矩阵，这样一直做到 \(f_1\)，得到新的答案。
复杂度 \(O(8n\log^2n)\)。
My Code
// Problem:
// P4719 【模板】"动态 DP"&动态树分治
//
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4719
// Memory Limit: 250 MB
// Time Limit: 1000 ms
#include<bits/stdc++.h>
#define ll long long
#define inf (1<<30)
#define INF (1ll<<60)
#define pii pair<int,int>
#define mkp make_pair
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define siz(a) (int)a.size()
#define pb emplace_back
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define pt(a) cerr<<#a<<'='<<a<<' '
#define pts(a) cerr<<#a<<'='<<a<<'\n'
//#define int long long
using namespace std;
const int MAXN=1e5+10;
struct Mat{
int a[3][3];
void con(int a11,int a12,int a21,int a22){
a[1][1]=a11;a[1][2]=a12;a[2][1]=a21;a[2][2]=a22;
}Mat friend operator*(Mat m1,Mat m2){
Mat ret;memset(ret.a,0,sizeof(ret.a));
rep(i,1,2) rep(k,1,2) rep(j,1,2)
ret.a[i][j]=max(ret.a[i][j],m1.a[i][k]+m2.a[k][j]);
return ret;
}
}M[MAXN],one;
int a[MAXN];
vector<int> e[MAXN];
int f[MAXN][2],g[MAXN][2],top[MAXN],ed[MAXN],fa[MAXN],son[MAXN];
int siz[MAXN],dep[MAXN],dfn[MAXN],rk[MAXN],tot;
struct SegTree{
struct Tree{int l,r;Mat m;}tr[MAXN<<2];
#define ls i<<1
#define rs i<<1|1
void pushup(int i){tr[i].m=tr[ls].m*tr[rs].m;}
void build(int i,int l,int r){
tr[i].l=l;tr[i].r=r;
if(l==r){tr[i].m=M[rk[l]];return;}
int mid=(l+r)>>1;build(ls,l,mid);build(rs,mid+1,r);
pushup(i);
}
void upd(int i,int x){
if(tr[i].l==tr[i].r){tr[i].m=M[rk[x]];return;}
int mid=(tr[i].l+tr[i].r)>>1;
if(x<=mid) upd(ls,x);else upd(rs,x);pushup(i);
}
Mat ask(int i,int l,int r){
if(l>r) return one;
if(tr[i].l==l&&tr[i].r==r) return tr[i].m;
int mid=(tr[i].l+tr[i].r)>>1;
if(r<=mid) return ask(ls,l,r);else if(l>mid) return ask(rs,l,r);
else return ask(ls,l,mid)*ask(rs,mid+1,r);
}
}T;
void dfs1(int x,int fat){
siz[x]=1;son[x]=-1;fa[x]=fat;
for(int s:e[x]){
if(s==fat) continue;
dep[s]=dep[x]+1;fa[s]=x;
dfs1(s,x);siz[x]+=siz[s];
if(son[x]==-1||siz[son[x]]<siz[s])
son[x]=s;
}
}
void dfs2(int x,int t){
dfn[x]=++tot;top[x]=t;rk[tot]=x;
if(son[x]==-1){ed[x]=x;return;}
dfs2(son[x],t);ed[x]=ed[son[x]];
for(int s:e[x]){
if(s==fa[x]||s==son[x]) continue;
dfs2(s,s);
}
}
void dfs(int x){
g[x][0]=a[x];g[x][1]=0;
for(int s:e[x]){
if(s==son[x]||s==fa[x]) continue;
dfs(s);
g[x][0]+=f[s][0];
g[x][1]+=max(f[s][0],f[s][1]);
}if(son[x]!=-1) dfs(son[x]);
f[x][0]=g[x][1]+max(f[son[x]][0],f[son[x]][1]);
f[x][1]=g[x][0]+f[son[x]][0];
}
void solve(){
int n,Q;cin>>n>>Q;
rep(i,1,n) cin>>a[i];
rep(i,2,n){
int u,v;cin>>u>>v;
e[u].pb(v);e[v].pb(u);
}
dfs1(1,0);dfs2(1,1);dfs(1);
rep(i,1,n) M[i].con(g[i][1],g[i][1],g[i][0],-inf);
T.build(1,1,n);
while(Q--){
int x,y;cin>>x>>y;
g[x][0]=g[x][0]-a[x]+y;a[x]=y;
M[x].con(g[x][1],g[x][1],g[x][0],-inf);
T.upd(1,dfn[x]);
while(x){
// pt(dfn[top[x]]);pts(dfn[ed[x]]-1);
Mat res=T.ask(1,dfn[top[x]],dfn[ed[x]]-1);
Mat ans;ans.con(0,0,a[ed[x]],0);ans=res*ans;
int p=fa[top[x]];
if(p){
g[p][0]=g[p][0]-f[top[x]][0]+ans.a[1][1];
g[p][1]=g[p][1]-max(f[top[x]][0],f[top[x]][1])+max(ans.a[1][1],ans.a[2][1]);
M[p].con(g[p][1],g[p][1],g[p][0],-inf);
T.upd(1,dfn[p]);
}f[top[x]][0]=ans.a[1][1];f[top[x]][1]=ans.a[2][1];
x=p;
}cout<<max(f[1][0],f[1][1])<<'\n';
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// int T;for(cin>>T;T--;)
one.con(0,-inf,-inf,0);
solve();
return 0;
}
总结
其实这个板子题并不简单。一般而言，DDP 是运用在序列上的，这样一来，转移式子和矩阵间就有了直接的联系了。
还有，通过例题和下面的习题你会发现，这里的矩阵应该是广义的。所以我们迫切地想知道什么样的矩阵是满足结合律的。我们把矩阵：
\[C_{i,j}=\bigoplus_{k=1}A_{i,k}\otimes B_{k,j} \]简写成矩阵 \(\{\oplus,\otimes\}\) 矩阵。那么这个广义矩阵满足结合律的条件是：
\(\otimes\) 有结合律，并且 \(\otimes\) 对 \(\oplus\) 有分配律。
可以验证一下，普通的矩阵都是 \(\{+,\times\}\) 矩阵，不难发现是成立的。包括上面例题中的 \(\{\max,+\}\)，也是成立的。
特别的，考虑一下 Floyd 算法，实际上也就是矩阵的乘法。所以我们把 \(\{\min,+\}\) 矩阵叫做 Floyd 矩阵把。
注意，在定义了广义矩阵之后，需要先自己思考单位矩阵是什么，然后再用它。
习题
首先考虑朴素的 dp。就是考虑用一个压位的状态来表示到当前这位为止，最少删除的字符数量。我们用 \(dp_{i,0\sim 4}\) 表示到第 \(i\) 位为止，使得它出现了 2016 的前 \(j\) 个字符所需要删去的最小字符数量。接下来我们讨论每一种字符的转移：
3,4,5,8,9，这些数与题目无关，所以直接留下即可。所以直接就是单位矩阵。2,0,1,7，需要对相应的 \(j\) 做出修改，并注意可以转移到下一个 \(j\)。6，这个数在 \(j=3,4\) 的时候必须被删去。
此时不难发现，我们构造的矩阵应当是个 Floyd 矩阵，即 \(\{\min,+\}\) 矩阵。
敏锐的你发现 \(k\le 5\)，于是直接把点按照 \(\lfloor\dfrac{a}{k}\rfloor\) 分组。这样每条边相当于修改一个转移矩阵，似乎比上面那题还要简单一点呢。
不难发现这还是一个 Floyd 矩阵，没连的边相当于正无穷就行了。
首先考虑链上的做法。显然有 \(dp_{i,0/1}\) 表示到节点 \(i\) 时无/有船的最小时间。那么有：
\[dp_{i,0}=\min(dp_{i-1,0}+a,dp_{i-1,1}+\min(a,a'))\\ dp_{i,1}=\min(dp_{i-1,0}+L+\min(a,a'),dp_{i-1,1}+a') \]这时候你发现只要对每条边赋一个矩阵，然后每次把路径上的矩阵全部乘起来就可以了。同样赋予一个 Floyd 矩阵。但是你注意到每条边对于不同的方向会有两种不同的转移矩阵。所以我们需要开 \(2\) 棵线段树来维护不同的方向。树剖的时候分讨一下就可以了。
为了维护边权，似乎需要边权转点权之后再上树剖。
注意矩乘的方向！