A Huster

0%

D-DP

Posted on Edited on Valine:

必备知识

​ 树链剖分,最大权独立集(即没有上司的舞会(树上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])$ ,如果我们将其改成矩阵乘的形式,就变成了下面这样;

​ 这个式子并不完整,这只是从一个点的矩阵乘,这个式子只是类似于矩阵乘,我们可以重新定义一下矩阵乘的定义,即将加法改为 $max$ ,将乘法改为加法,那么就可以通项递推了;

​ 但是这个式子只限于从一个点递推过来,那么其他点怎么办?

​ 没有办法…但是这是一个思路,这个式子用线段树维护,可以让我们可以快速处理出链上信息.

​ 既然在树上,我们不如将重链看成这个链,而将链上的轻儿子的信息提前处理出来,在重链上的点的信息通过进行矩阵速推.

​ (注: $f’[x][0]$ 是点 $x$ 只处理轻儿子和自己信息时的值)

​ 那么如何修改?

​ 同一条重链上点的修改对于这条链上的点是没有影响的,因为重链每个点只保存其轻儿子的信息,有影响的是对于这条链 $top$ 的父亲节点,那么我们的思路就出来了,修改点时,修改链 $top$ 父亲的矩阵信息即可;

​ 总结一下思路: 首先将DP式子化为通项矩阵乘的形式,先处理出每个节点轻儿子的信息,在树上用树链剖分维护链上矩阵乘信息,修改时,每次修改链首父亲的矩阵值,修改至树根重链.修改细节即修改点信息,之后从链尾到链首矩阵乘,与之前的值作差修改.最后求答案时直接处理链上信息即可;

code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
#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式子变成矩阵乘的形式,用数据结构进行维护,其高效并支持拓展;

本站访问次数：