必备知识
树链剖分,最大权独立集(即没有上司的舞会(树上DP)),矩阵乘法;
D-DP
模版简述
模板
关于动态DP,其实是关于一类动态修改点权的问题,但是很难去处理;
我们平常的DP经常是离线DP,而当在线时,就会出现事故;
D-DP是关于求最大权独立集的,支持动态修改点值,其思想即DP的通项递推式改为矩阵乘的形式进行递推,而树上问题就可以使用树链剖分提前处理出区间矩阵乘;
大家肯定都会 \(O(nm)\) 做法,即暴力修改点值进行DP.
求最大权独立集的DP式子为 \(f[x][1]=\sum f[y][0] , f[x][0]=\sum max(f[y][1],f[y][0])\) ,如果我们将其改成矩阵乘的形式,就变成了下面这样;
\[[^{f[y][0]}_{f[y][1]}] * [^{0,0}_{v[x],-inf}]=[^{f[x][0]}_{f[x][1]}]
\]
这个式子并不完整,这只是从一个点的矩阵乘,这个式子只是类似于矩阵乘,我们可以重新定义一下矩阵乘的定义,即将加法改为 \(max\) ,将乘法改为加法,那么就可以通项递推了;
但是这个式子只限于从一个点递推过来,那么其他点怎么办?
没有办法…但是这是一个思路,这个式子用线段树维护,可以让我们可以快速处理出链上信息.
既然在树上,我们不如将重链看成这个链,而将链上的轻儿子的信息提前处理出来,在重链上的点的信息通过进行矩阵速推.
\[[^{f[y][0]}_{f[y][1]}]*[^{f'[x][0],f'[x][0]}_{f'[x][1],-inf}]=[^{f[x][0]}_{f[x][1]}]
\]
(注: \(f'[x][0]\) 是点 \(x\) 只处理轻儿子和自己信息时的值)
那么如何修改?
同一条重链上点的修改对于这条链上的点是没有影响的,因为重链每个点只保存其轻儿子的信息,有影响的是对于这条链 \(top\) 的父亲节点,那么我们的思路就出来了,修改点时,修改链 \(top\) 父亲的矩阵信息即可;
总结一下思路: 首先将DP式子化为通项矩阵乘的形式,先处理出每个节点轻儿子的信息,在树上用树链剖分维护链上矩阵乘信息,修改时,每次修改链首父亲的矩阵值,修改至树根重链.修改细节即修改点信息,之后从链尾到链首矩阵乘,与之前的值作差修改.最后求答案时直接处理链上信息即可;
code
#include<bits/stdc++.h>
#define le(p) p<<1
#define re(p) p<<1|1
#define ll long long
using namespace std;
const int maxn=1e5+7,inf=1e9;
int n,m,head[maxn],son[maxn],top[maxn],bot[maxn],fl[maxn];
int fa[maxn],id[maxn],cent,tot,a[maxn],sz[maxn],f[maxn][2];
struct node{
int next,to;
}edge[maxn<<1];
struct matrix{
ll g[2][2];
matrix operator *(const matrix x) const{
matrix ans;
ans.g[0][0]=max(g[0][0]+x.g[0][0],g[0][1]+x.g[1][0]);
ans.g[0][1]=max(g[0][0]+x.g[0][1],g[0][1]+x.g[1][1]);
ans.g[1][0]=max(g[1][0]+x.g[0][0],g[1][1]+x.g[1][0]);
ans.g[1][1]=max(g[1][0]+x.g[0][1],g[1][1]+x.g[1][1]);
return ans;
}//矩阵乘
}tr[maxn<<2];
matrix ori[maxn];template<typename type_of_scan>
inline void scan(type_of_scan &x){
type_of_scan f=1;x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
x*=f;
}
template<typename top,typename... tops>
inline void scan(top &x,tops&... X){
scan(x),scan(X...);
}inline void add(int u,int v){
edge[++cent]=(node){head[u],v};head[u]=cent;
edge[++cent]=(node){head[v],u};head[v]=cent;
}
//树链剖分预处理
void dfs1(int x){
sz[x]=1;
for(int i=head[x];i;i=edge[i].next){
int y=edge[i].to;
if(y==fa[x]) continue;
fa[y]=x,dfs1(y);
sz[x]+=sz[y];
if(sz[y]>sz[son[x]]) son[x]=y;
}
}void dfs2(int x,int tp){
id[x]=++tot,fl[tot]=x;top[x]=tp;
if(son[x]) dfs2(son[x],tp),bot[x]=bot[son[x]];
else return bot[x]=x,void();
for(int i=head[x];i;i=edge[i].next){
int y=edge[i].to;
if(y==fa[x]||y==son[x]) continue;
dfs2(y,y);
}
}
//树上DP
void dfs3(int x){
f[x][0]=0;f[x][1]=a[x];
for(int i=head[x];i;i=edge[i].next){
int y=edge[i].to;
if(y==fa[x]) continue;
dfs3(y);
f[x][0]+=max(f[y][0],f[y][1]);
f[x][1]+=f[y][0];
}
}void push_up(int p){
tr[p]=tr[le(p)]*tr[re(p)];
}
//建树时每个点只保存自己和轻儿子的信息
void build(int l,int r,int p){
if(l==r){
tr[p].g[0][0]=tr[p].g[0][1]=0;tr[p].g[1][1]=-inf;
tr[p].g[1][0]=a[fl[l]];int x=fl[l];
for(int i=head[x];i;i=edge[i].next){
int y=edge[i].to;
if(y==fa[x]||y==son[x]) continue;
tr[p].g[0][0]+=max(f[y][0],f[y][1]);
tr[p].g[1][0]+=f[y][0];
}
tr[p].g[0][1]=tr[p].g[0][0];
ori[fl[l]]=tr[p];
return ;
}
int mid=l+r>>1;
build(l,mid,le(p));build(mid+1,r,re(p));
push_up(p);
}void add(int x,int l,int r,int p){
if(l==r) return tr[p]=ori[fl[l]],void();
int mid=l+r>>1;
if(x<=mid) add(x,l,mid,le(p));
else add(x,mid+1,r,re(p));
push_up(p);
}matrix query(int nl,int nr,int l,int r,int p){
if(nl<=l&&r<=nr) return tr[p];
int mid=l+r>>1;
if(nl<=mid&&mid<nr) return query(nl,nr,l,mid,le(p))*query(nl,nr,mid+1,r,re(p));
else if(nl<=mid) return query(nl,nr,l,mid,le(p));
else return query(nl,nr,mid+1,r,re(p));
}matrix query(int x){
return query(id[top[x]],id[bot[x]],1,n,1);
}matrix solve(int x,int k){
ori[x].g[1][0]+=k-a[x];a[x]=k;
while(x){
matrix old,news;
old=query(top[x]);//没修改的
add(id[x],1,n,1);//change
news=query(top[x]);//修改过的
x=fa[top[x]];if(!x) break;
ori[x].g[0][0]+=max(news.g[0][0],news.g[1][0])-max(old.g[0][0],old.g[1][0]);
ori[x].g[0][1]=ori[x].g[0][0];
ori[x].g[1][0]+=news.g[0][0]-old.g[0][0];
}
return query(1);
}int main(){
scan(n,m);
for(int i=1;i<=n;i++) scan(a[i]);
for(int i=1,u,v;i<=n-1;i++)
scan(u),scan(v),add(u,v);
dfs1(1),dfs2(1,1),dfs3(1);build(1,n,1);
while(m--){
int x,k;
scan(x,k);
matrix ans=solve(x,k);
printf("%d\n",max(ans.g[0][0],ans.g[1][0]));
}
return 0;
}
例题
[NOIP2018]保卫王国;
有两个点,强制选点或强制不选,求最小覆盖集;
最小覆盖集=全集-最大权独立集;
强制选点或不选可以通过将其改为 \(-inf\) 和 \(inf\) ,之后就是D-DP模板了;
code
#include<bits/stdc++.h>
#define ll long long
#define le(x) x<<1
#define re(x) x<<1|1
using namespace std;
const int maxn=1e5+7;
const ll inf=1e9;
int n,m,fa[maxn],id[maxn],fl[maxn],sz[maxn],head[maxn];
int son[maxn],top[maxn],cent,tot,bot[maxn];
ll f[maxn][2],a[maxn],sum,ans;
vector<int>to[maxn];
char type[2];
struct node{
int next,to;
}edge[maxn<<1];
struct matrix{
ll g[2][2];
matrix operator *(const matrix x) const{
matrix ans;
ans.g[0][0]=max(g[0][0]+x.g[0][0],g[0][1]+x.g[1][0]);
ans.g[0][1]=max(g[0][0]+x.g[0][1],g[0][1]+x.g[1][1]);
ans.g[1][0]=max(g[1][0]+x.g[0][0],g[1][1]+x.g[1][0]);
ans.g[1][1]=max(g[1][0]+x.g[0][1],g[1][1]+x.g[1][1]);
return ans;
}
}tr[maxn<<3];
matrix ori[maxn];template<typename type_of_scan>
inline void scan(type_of_scan &x){
type_of_scan f=1;x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
x*=f;
}
template<typename top,typename... tops>
inline void scan(top &x,tops&... X){
scan(x),scan(X...);
}inline void add(int u,int v){
edge[++cent]=(node){head[u],v};head[u]=cent;
edge[++cent]=(node){head[v],u};head[v]=cent;
to[u].push_back(v),to[v].push_back(u);
}void dfs1(int x){
sz[x]=1;
for(int i=head[x];i;i=edge[i].next){
int y=edge[i].to;
if(y==fa[x]) continue;
fa[y]=x;dfs1(y);
sz[x]+=sz[y];
if(sz[y]>sz[son[x]]) son[x]=y;
}
}void dfs2(int x,int tp){
id[x]=++tot,fl[tot]=x,top[x]=tp;
if(son[x]) dfs2(son[x],tp),bot[x]=bot[son[x]];
else return bot[x]=x,void();
for(int i=head[x];i;i=edge[i].next){
int y=edge[i].to;
if(y==fa[x]||y==son[x]) continue;
dfs2(y,y);
}
}void dfs3(int x){
f[x][1]=a[x],f[x][0]=0;
for(int i=head[x];i;i=edge[i].next){
int y=edge[i].to;
if(y==fa[x]) continue;
dfs3(y);
f[x][0]+=max(f[y][0],f[y][1]);
f[x][1]+=f[y][0];
}
}void push_up(int p){
tr[p]=tr[le(p)]*tr[re(p)];
}void build(int l,int r,int p){
if(l==r){
tr[p].g[0][0]=tr[p].g[0][1]=0;int x=fl[l];
tr[p].g[1][0]=a[fl[l]];tr[p].g[1][1]=-inf;
for(int i=head[x];i;i=edge[i].next){
int y=edge[i].to;
if(y==fa[x]||y==son[x]) continue;
tr[p].g[0][0]+=max(f[y][0],f[y][1]);
tr[p].g[1][0]+=f[y][0];
}
tr[p].g[0][1]=tr[p].g[0][0];
ori[fl[l]]=tr[p];
return ;
}
int mid=l+r>>1;
build(l,mid,le(p)),build(mid+1,r,re(p));
push_up(p);
}void add(int x,int l,int r,int p){
if(l==r) return tr[p]=ori[fl[l]],void();
int mid=l+r>>1;
if(x<=mid) add(x,l,mid,le(p));
else add(x,mid+1,r,re(p));
push_up(p);
}matrix query(int nl,int nr,int l,int r,int p){
if(nl<=l&&r<=nr) return tr[p];
int mid=l+r>>1;
if(nl<=mid&&mid<nr) return query(nl,nr,l,mid,le(p))*query(nl,nr,mid+1,r,re(p));
else if(nl<=mid) return query(nl,nr,l,mid,le(p));
else return query(nl,nr,mid+1,r,re(p));
}matrix query(int x){
return query(id[top[x]],id[bot[x]],1,n,1);
}void modify(int x,ll k){
ori[x].g[1][0]+=k-a[x];a[x]=k;
while(x){
matrix old,news;
old=query(top[x]);add(id[x],1,n,1);
news=query(top[x]);
x=fa[top[x]];if(!x) break;
ori[x].g[0][0]+=max(news.g[0][0],news.g[1][0])-max(old.g[0][0],old.g[1][0]);
ori[x].g[0][1]=ori[x].g[0][0];
ori[x].g[1][0]+=news.g[0][0]-old.g[0][0];
}
return ;
}int main(){
scan(n,m);cin>>type;
for(int i=1;i<=n;i++) scan(a[i]),sum+=a[i];
for(int i=1,u,v;i<=n-1;i++)
scan(u),scan(v),add(u,v);
for(int i=1;i<=n;i++) sort(to[i].begin(),to[i].end());
dfs1(1),dfs2(1,1),dfs3(1),build(1,n,1);
while(m--){
int f1,f2,g1,g2,t1,t2;
scan(f1,f2,g1,g2);
if(f2==g2&&!f2){
vector<int>::iterator pos=lower_bound(to[f1].begin(),to[f1].end(),g1);
if(pos!=to[f1].end()&&(*pos)==g1){
puts("-1");continue;
}
}
t1=a[f1],t2=a[g1];
modify(f1,f2?-inf:inf);
modify(g1,g2?-inf:inf);
matrix ol=query(1);
ans=max(ol.g[0][0],ol.g[1][0]);
if(!f2) ans=ans-inf+t1;
if(!g2) ans=ans-inf+t2;
printf("%lld\n",sum-ans);
modify(f1,t1),modify(g1,t2);
}
return 0;
}
当然还有倍增做法,但这里不再讲述,D-DP中一个重要思想就是讲DP式子变成矩阵乘的形式,用数据结构进行维护,其高效并支持拓展;
