动态dp（ddp）

“天外之路神秘莫测，但这无法成为少年止步的借口。”

引言

这类题的第一次见面在于P5662 [CSP-J2019] 纪念品，当时年少无知的我听说高年级有一位神仙切了这道题，这道题是个动态动态规划，对于只学了搜索的我只能瑟瑟发抖。（但实际上只是道不好想的背包罢了）然后第二次见面就在不久之前，P8820 [CSP-S 2022] 数据传输名副其实的动态 ，用于解决树论问题的思想，结合树剖和矩乘。

想着要把这次考试的题在 前给自己个交代，只剩 没改，贺题解又不太现实，就趁着某日晚闲暇，学了这玩意儿。

动态树分治

动态 ，又称动态树分治。（虽然不知道是动态树分治还是动态树分治）是某神仙（发明了猫树的那个）在某年 讲的黑科技，用于解决树上点边权带修的动态规划问题。

广义矩阵乘法

我们知道，定义矩阵 有 的话，应该有 ，这是狭义下的矩阵乘法，现在我们定义一个操作 为： 实意为 ，也就是把矩阵乘法的 变为 ，把 变为 ，但实际形式与矩阵乘法相似，且性质与矩阵乘法相似，我们称之为广义矩阵乘法（俗称广义矩乘）。

形如 其中 都是一种运算，且满足这两个运算的结合满足结合律。

例题

前置芝士

万能的洛谷当然有模板题。乍一看，如果不算上修改操作的话，这个题和「没有上司的舞会」应该是一个级别的，但如果有修改的话，用同样的方法应该就是 级别的了，这是根本不可能完成的操作。

但是在模板题里喜闻乐见有了 。

参考代码

const int MAXN=1e3+10;
const int INF=0x3f3f3f3f;
int N,Q,Val[MAXN];
int Dp[MAXN][2];
struct G
{
	int next,to;
}Edge[MAXN<<1];
int Head[MAXN],Total;
inline void addEdge(int u,int v)
{
	Edge[++Total]=(G){Head[u],v};Head[u]=Total;
	Edge[++Total]=(G){Head[v],u};Head[v]=Total;
}
inline void init()
{
	for(int i=1;i<=N;++i) Dp[i][0]=0,Dp[i][1]=-INF;
}
void dpTree(int x,int last)
{
	Dp[x][1]=Val[x];
	for(int e=Head[x],v;e;e=Edge[e].next)
	{
		if((v=Edge[e].to)==last) continue;
		dpTree(v,x);
		checkMax(Dp[x][0],Dp[x][0]+std::max(Dp[v][0],Dp[v][1]));
		checkMax(Dp[x][1],Dp[x][1]+Dp[v][0]);
	}
}
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
	read(N,Q);
	for(int i=1;i<=N;++i) read(Val[i]);
	for(int i=2,u,v;i<=N;++i){ read(u,v);addEdge(u,v); }
	for(int qx,qy;Q--;)
	{
		read(qx,qy);Val[qx]=qy;
		init();dpTree(1,0);
		write(std::max(Dp[1][0],Dp[1][1]),'\n');
	}
	return 0;
}

我们先来回顾「没有上司的舞会」的做题思路，记 表示以 为根结点的子树内 结点是否参加的最大答案，则有转移方程：

$$\begin{cases} \displaystyle dp[u][1]=1+\sum_{fa(v)=u}dp[v][0] \\ \displaystyle dp[u][0]=\max_{fa(v)=u}\{dp[v][1],dp[v][0]\} \end{cases}\nonumber$$

最终答案为 。

这是显然的，而在后来的学习中我们也了解到，这也是求解树上最大权独立集的 方法（网络流我们不提及，毕竟那个复杂度可能有些高）。

题解

考虑每一次修改对答案的贡献：我们发现，修改 的权值至多会影响 到根结点的 值，也就是在随机数据下只会影响至多 个结点，其它 值是不变的，但显然，树可能会退化成链或者蒲公英，那么修改点数又会变成 。（但这道题这么做似乎能过）

那我们首先考虑如何提取链来进行操作：进行树链剖分，这是树上路径操作的基本操守。我们考虑重链剖分，这样一棵树内只会存在 个重儿子结点，每一个点到达根结点的路径也至多存在 个轻儿子，这些都是一些能够帮助我们的性质。

那么，我们需要考虑如何把 过程贴到树剖上去。

考虑利用轻重儿子的性质：记录 来针对轻儿子的选择，即 表示 结点的所有轻儿子都不被选取的最大权独立集，而 表示 结点的轻儿子可取可不取的最大权独立集。

这样的话，可以将转移方程这样写：

$$\begin{cases} dp[i][0]=g_{i,0}+\max\{dp[j][0],dp[j][1]\}&,j\in heavyson(i) \\ dp[i][1]=g_{i,1}+val_i+dp[j][0]&,j\in heavyson(i) \end{cases}\nonumber$$

初始化为 。

然后玄学优化，重定义 ：

• 表示不选择 结点以及 结点的重儿子，只允许选择 结点的轻儿子的以 为根结点的子树的最大贡献；
• 表示不考虑 结点的重儿子（即不选择 的重儿子）的以 为根结点的子树的最大贡献。

那么我们就可以优化方程：

$$\begin{cases} dp[u][0]=g_{u,0}+\max\{dp[v][0],dp[v][1]\}&,v=son_u \\ dp[u][1]=g_{u,1}+dp[v][0]&,v=son_u \end{cases}\nonumber$$

这样不考虑常数项的转移方程似乎就很优美了。仅和 相关的式子，可以考虑用个什么东西来优化：我们从 转移到 ，因为一个结点至多有 个重儿子，所以转移路径唯一，这是一个递推式。

考虑矩阵加速。

但是考虑到这并不是矩乘常见的 格式，所以考虑广义矩乘加速，定义为 ，然后我们想方设法把 操作套到所有转移上使其能够供我们矩乘加速：

$$\begin{cases} dp[u][0]=\max\{dp[v][0]+g_{u,0},dp[v][1]+g_{u,0} \}&,v=son_u\ \\ dp[u][1]=\max\{g_{i,1}+dp[v][0],-\infty \}&,v=son_u \end{cases}\nonumber$$

实际上就是将 外的操作都移植到了 的可控范围内，然后想办法在这个基础上进行转移，设我们当前需要的转移矩阵为 ：

$$\begin{vmatrix} dp_{v,0},dp_{v,1} \end{vmatrix} \times A= \begin{vmatrix} dp_{u,0},dp_{u,1} \end{vmatrix} \nonumber$$

然后就考虑如何构造 了。首先要注意的是——此处的 并非常规矩乘，而是我们定义的广义矩乘中的 二元组，所以在推导的时候要格外注意，最后得到的是这样的一个 的转移矩阵：

$$\begin{vmatrix} dp_{v,0}\\dp_{v,1} \end{vmatrix} \times \begin{vmatrix} g_{u,0}& g_{u,0} \\ g_{u,1}& -\infty \end{vmatrix} = \begin{vmatrix} dp_{u,0}\\dp_{u,1} \end{vmatrix} \nonumber$$

最后将这个矩乘加速运用到动态树分治里去：现在的叶结点是通过了初始化，也就记录了最原始的（未经过任何修改的 值）答案，而链中结点则记录了一个转移矩阵，这个矩阵与树链剖分的本身信息并不冲突，也就意味着这个矩阵不受重链限制。

而这个矩阵是满足合并性质（也就是结合律），所以可以用树剖通常的方法维护线段树矩乘然后合并。而当我们跳链的时候，因为当前的链头实际上是它父亲的轻儿子，所以需要更新其父亲结点的转移矩阵，直到根结点。这样的话，每一次操作至多更新 个矩阵，最终的复杂度为 其中 为矩阵。

考虑如何用已知信息维护这个玩意儿，用重剖求出 序，根据树剖性质，每一条链的 序连续，且子树 序一定比根小。这样可以进一步将矩阵进行序列型维护，使代码实现稍微简单一些。

但实际上还是还是很麻烦。

有几个坑点，读者可以注意：

• 矩阵的下标看个人喜好，贺题的时候不要贺错了。
• 贺板子的时候请确保板子是对的。
• 不要把 continue; 写成 return ; 了。

AC Code

// ----- Eternally question-----
// Problem: P4719 【模板】"动态 DP"&动态树分治
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4719
// Memory Limit: 250 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2022-11-16 20:53:07
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e5+10;
const int INF=0x3f3f3f3f;
int N,Q,Pt[MAXN];
int Dp[MAXN][2];
struct Matrix
{
	int mat[2][2];
	Matrix(){ memset(mat,-0x3f,sizeof(mat)); }
	inline Matrix operator*(Matrix b)
	{
		Matrix c;
		for(int i=0;i<2;++i)
			for(int j=0;j<2;++j)
				for(int k=0;k<2;++k)
					checkMax(c.mat[i][j],mat[i][k]+b.mat[k][j]);
		return c;
	}
}Val[MAXN];
struct G
{
	int next,to;
}Edge[MAXN<<1];
int Head[MAXN],Total;
inline void addEdge(int u,int v)
{
	Edge[++Total]=(G){Head[u],v};Head[u]=Total;
	Edge[++Total]=(G){Head[v],u};Head[v]=Total;
}
int Fa[MAXN],Dep[MAXN],Siz[MAXN],Son[MAXN];
void dfsTree(int x,int last)
{
	Fa[x]=last,Dep[x]=Dep[last]+1,Siz[x]=1;
	for(int e=Head[x],v;e;e=Edge[e].next)
	{
		if((v=Edge[e].to)==last) continue;
		dfsTree(v,x);
		Siz[x]+=Siz[v];
		if(!Son[x]||Siz[v]>Siz[Son[x]]) Son[x]=v;
	}
}
int Top[MAXN],Dfn[MAXN],Bck[MAXN],End[MAXN],Cnt;
void dfsChain(int x,int topf)
{
	Top[x]=topf,Dfn[x]=++Cnt;Bck[Cnt]=x;
	Dp[x][0]=0,Dp[x][1]=Pt[x];
	Val[x].mat[0][0]=Val[x].mat[0][1]=0;
	Val[x].mat[1][0]=Pt[x];
	checkMax(End[topf],Cnt);
	if(!Son[x]) return ;
	dfsChain(Son[x],topf);
	Dp[x][0]+=std::max(Dp[Son[x]][0],Dp[Son[x]][1]);
	Dp[x][1]+=Dp[Son[x]][0];
	for(int e=Head[x],v;e;e=Edge[e].next)
	{
		if((v=Edge[e].to)==Fa[x]||v==Son[x]) continue;
		dfsChain(v,v);
		Dp[x][0]+=std::max(Dp[v][0],Dp[v][1]);
		Dp[x][1]+=Dp[v][0];
		Val[x].mat[0][0]+=std::max(Dp[v][0],Dp[v][1]);
		Val[x].mat[0][1]=Val[x].mat[0][0];
		Val[x].mat[1][0]+=Dp[v][0];
	}
}
#define ls (p<<1)
#define rs (p<<1|1)
struct ST
{
	int l,r;
	Matrix val;
}Tr[MAXN<<2];
inline void pushUp(int p)
{
	Tr[p].val=Tr[ls].val*Tr[rs].val;
}
void build(int p,int l,int r)
{
	Tr[p].l=l,Tr[p].r=r;
	if(l==r) return Tr[p].val=Val[Bck[l]],void();
	int mid=(l+r)>>1;
	build(ls,l,mid),build(rs,mid+1,r);
	pushUp(p);
}
void modifyX(int p,int x)
{
	if(Tr[p].l==Tr[p].r) return Tr[p].val=Val[Bck[x]],void();
	int mid=(Tr[p].l+Tr[p].r)>>1;
	if(x<=mid) modifyX(ls,x);
	else modifyX(rs,x);
	pushUp(p);
}
Matrix queryMul(int p,int l,int r)
{
	if(l==Tr[p].l&&Tr[p].r==r) return Tr[p].val;
	int mid=(Tr[p].l+Tr[p].r)>>1;Matrix res;
	if(r<=mid) return queryMul(ls,l,r);
	else if(mid<l) return queryMul(rs,l,r);
	else return queryMul(ls,l,mid)*queryMul(rs,mid+1,r);
}
inline void modifyPath(int x,int v)
{
	Val[x].mat[1][0]+=v-Pt[x];Pt[x]=v;
	Matrix bef,aft;
	while(x!=0)
	{
		bef=queryMul(1,Dfn[Top[x]],End[Top[x]]);
		modifyX(1,Dfn[x]);
		aft=queryMul(1,Dfn[Top[x]],End[Top[x]]);
		x=Fa[Top[x]];
		Val[x].mat[0][0]+=std::max(aft.mat[0][0],aft.mat[1][0])-std::max(bef.mat[0][0],bef.mat[1][0]);
		Val[x].mat[0][1]=Val[x].mat[0][0];
		Val[x].mat[1][0]+=aft.mat[0][0]-bef.mat[0][0];
	}
}
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
	read(N,Q);
	for(int i=1;i<=N;++i) read(Pt[i]);
	for(int i=2,u,v;i<=N;++i){ read(u,v);addEdge(u,v); }
	dfsTree(1,0),dfsChain(1,1);
	build(1,1,N);
	for(int qx,qv;Q--;)
	{
		read(qx,qv);
		modifyPath(qx,qv);
		Matrix ans=queryMul(1,Dfn[1],End[1]);
		write(std::max(ans.mat[0][0],ans.mat[1][0]),'\n');
	}
	return 0;
}
/*

*/

我们可以把树型 的预处理单独跑一遍 dfs ，也可以放在树剖的第二次 dfs 里解决（不能放第一次的原因在于第一次的时候轻重儿子还没有被钦定）。

另话

这道题有一个强制在线的加强版，使得 和树链剖分都过不去（当然有神仙可以卡过去），会用到一种叫做全局平衡二叉树的东西，我们之后再讨论（大概 后？）。

---

扩展

保卫王国

首先有一个显而易见的结论：最小点权覆盖集等于全集减去最大点权独立集。

所以就可以转化成「没有上司的舞会」问题，但是每次询问会固定掉两个点，这对 是极其难搞的问题，但我们可以考虑把这两个点权值赋为 ，让其强制（不）被选择。

那就是个动态树分治的板子题了。

AC Code

// ----- Eternally question-----
// Problem: P5024 [NOIP2018 提高组] 保卫王国
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5024
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// Written by: Eternity
// Time: 2022-11-17 11:32:25
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e5+10;
const int INF=0x3f3f3f3f;
int N,Q;
ll Pt[MAXN],Sum,Dp[MAXN][2];
char Opt[3];
struct G
{
	int next,to;
}Edge[MAXN<<1];
int Head[MAXN],Total;
inline void addEdge(int u,int v)
{
	Edge[++Total]=(G){Head[u],v};Head[u]=Total;
	Edge[++Total]=(G){Head[v],u};Head[v]=Total;
}
struct Matrix
{
	ll mat[2][2];
	Matrix(){ memset(mat,-0x3f,sizeof(mat)); }
	Matrix operator*(Matrix b)
	{
		Matrix c;
		for(int i=0;i<2;++i)
			for(int j=0;j<2;++j)
				for(int k=0;k<2;++k)
					checkMax(c.mat[i][j],mat[i][k]+b.mat[k][j]);
		return c;
	}
}Val[MAXN];
int Fa[MAXN],Dep[MAXN],Siz[MAXN],Son[MAXN];
void dfsTree(int x,int last)
{
	Fa[x]=last,Dep[x]=Dep[last]+1,Siz[x]=1;
	for(int e=Head[x],v;e;e=Edge[e].next)
	{
		if((v=Edge[e].to)==last) continue;
		dfsTree(v,x);
		Siz[x]+=Siz[v];
		if(!Son[x]||Siz[v]>Siz[Son[x]]) Son[x]=v;
	}
}
int Top[MAXN],Dfn[MAXN],Bck[MAXN],End[MAXN],Cnt;
void dfsChain(int x,int topf)
{
	Top[x]=topf,Dfn[x]=++Cnt;Bck[Cnt]=x;
	Dp[x][0]=0,Dp[x][1]=Pt[x];
	Val[x].mat[0][1]=Val[x].mat[0][0]=0;
	Val[x].mat[1][0]=Pt[x];
	checkMax(End[topf],Cnt);
	if(!Son[x]) return ;
	dfsChain(Son[x],topf);
	Dp[x][0]+=std::max(Dp[Son[x]][0],Dp[Son[x]][1]);
	Dp[x][1]+=Dp[Son[x]][0];
	for(int e=Head[x],v;e;e=Edge[e].next)
	{
		if((v=Edge[e].to)==Fa[x]||v==Son[x]) continue;
		dfsChain(v,v);
		Dp[x][0]+=std::max(Dp[v][0],Dp[v][1]);
		Dp[x][1]+=Dp[v][0];
		Val[x].mat[0][0]+=std::max(Dp[v][0],Dp[v][1]);
		Val[x].mat[0][1]=Val[x].mat[0][0];
		Val[x].mat[1][0]+=Dp[v][0];
	}
}
#define ls (p<<1)
#define rs (p<<1|1)
struct ST
{
	int l,r;
	Matrix val;
}Tr[MAXN<<2];
inline void pushUp(int p)
{
	Tr[p].val=Tr[ls].val*Tr[rs].val;
}
void build(int p,int l,int r)
{
	Tr[p].l=l,Tr[p].r=r;
	if(l==r) return Tr[p].val=Val[Bck[l]],void();
	int mid=(l+r)>>1;
	build(ls,l,mid),build(rs,mid+1,r);
	pushUp(p);
}
void modifyX(int p,int x)
{
	if(Tr[p].l==Tr[p].r) return Tr[p].val=Val[Bck[x]],void();
	int mid=(Tr[p].l+Tr[p].r)>>1;
	if(x<=mid) modifyX(ls,x);
	else modifyX(rs,x);
	pushUp(p);
}
Matrix queryMul(int p,int l,int r)
{
	if(l==Tr[p].l&&Tr[p].r==r) return Tr[p].val;
	int mid=(Tr[p].l+Tr[p].r)>>1;
	if(r<=mid) return queryMul(ls,l,r);
	else if(mid<l) return queryMul(rs,l,r);
	else return queryMul(ls,l,mid)*queryMul(rs,mid+1,r);
}
inline void modifyPath(int x,int v)
{
	// Val[x].mat[1][0]+=v-Pt[x];Pt[x]=v;
	Val[x].mat[1][0]+=v,Pt[x]+=v;
	Matrix bef,aft;
	while(x)
	{
		bef=queryMul(1,Dfn[Top[x]],End[Top[x]]);
		modifyX(1,Dfn[x]);
		aft=queryMul(1,Dfn[Top[x]],End[Top[x]]);
		x=Fa[Top[x]];
		Val[x].mat[0][0]+=std::max(aft.mat[0][0],aft.mat[1][0])-std::max(bef.mat[0][0],bef.mat[1][0]);
		Val[x].mat[0][1]=Val[x].mat[0][0];
		Val[x].mat[1][0]+=aft.mat[0][0]-bef.mat[0][0];
	}
}
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
	read(N,Q);scanf("%s",Opt);
	for(int i=1;i<=N;++i) read(Pt[i]),Sum+=Pt[i];
	for(int i=2,u,v;i<=N;++i){ read(u,v);addEdge(u,v); }
	dfsTree(1,0),dfsChain(1,1);
	build(1,1,N);
	for(int qx1,qv1,qx2,qv2;Q--;)
	{
		read(qx1,qv1,qx2,qv2);
		if((Fa[qx1]==qx2||Fa[qx2]==qx1)&&(!qv1)&&(!qv2))
		{
			puts("-1");
			continue;
		}
		modifyPath(qx1,qv1?-INF:INF),modifyPath(qx2,qv2?-INF:INF);
		Matrix ans=queryMul(1,Dfn[1],End[1]);
		ll res=Sum-std::max(ans.mat[0][0],ans.mat[1][0])+(qv1?0:INF)+(qv2?0:INF);
		write(res,'\n');
		modifyPath(qx1,qv1?INF:-INF),modifyPath(qx2,qv2?INF:-INF);
	}
	return 0;
}
/*

*/

---

数据传输

更新于同名博客。

---