YbtOJ「动态规划」第4章 树形DP

YbtOJ 大全

【例题1】树上求和

设 $f[u][0]$ 表示这个点不选，$f[u][1]$ 表示这个点选。

那么转移方程 $f[u][0]+=\max (f[v][0],f[v][1])$，$f[u][1]=f[v][0]+a[u]$。最后的答案就是 $ans=\max (ans,\max (f[u][0],f[u][1]))$。

#include 
#include 
#include 
#include 
#include 
#define re register
#define int long long 
#define drep(a,b,c) for(re int a(b) ; a>=(c) ; --a)
#define rep(a,b,c) 	for(re int a(b) ; a<=(c) ; ++a)
using namespace std;
inline int read(){
   
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){
   if(ch == '-') f=-1 ; ch=getchar();}
	while(ch>='0'&&ch<='9'){
   x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
inline void print(int x){
   
	if(x < 0) putchar('-'),x = -x;
	if(x >= 10) print(x / 10);
	putchar(x % 10 + '0');
}
const int M = 2e4+10;
int head[M],f[M][2],a[M];
int n,cnt,ans = 1;
struct edge{
   
	int to,nxt;
}e[M];
inline void add(int u,int v){
   
	e[++cnt].to = v;
	e[cnt].nxt = head[u];
	head[u] = cnt;
}
inline void dfs(int u,int fa){
   
	f[u][1] = a[u],f[u][0] = 0;
	for(re int i(head[u]) ; i ; i=e[i].nxt){
   
		int v = e[i].to;
		if(v == fa) continue;
		dfs(v,u);
		f[u][0] += max(f[v][0],f[v][1]);
		f[u][1] = f[v][0] + a[u];
		ans = max(ans,max(f[u][0],f[u][1]));
	}
}
signed main(){
   
	n = read();
	rep(i,1,n) a[i] = read();
	rep(i,1,n-1){
   
		int u = read(),v = read();
		add(v,u),add(u,v);
	}
	dfs(1,0);
	printf("%d\n",ans);
	return 0;
}
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

【例题2】结点覆盖

设 $f[u][0]$ 选 $u$ 的父亲结点，$f[u][1]$ 表示选 $u$ 自己，$f[u][2]$ 表示选 $u$ 的儿子。

• 若 $u$ 被其父结点覆盖，那么子结点只能被其子结点或其本身覆盖。$f[u][0]+=\min (f[v][1],f[v][2])$
• 若 $u$ 被其本身覆盖，那它的子结点可以被其父亲或自己或孩子覆盖。$f[u][1]+=\min (f[v][0],\min (f[v][1],f[v][2]))$
• 若 $u$ 被其子结点覆盖。由于至少要选一个子结点，其余的子结点可以被其子结点或本身覆盖。我们用一个变量记录是否选了 $u$ 的一个子结点。如果都没有选，只能选最小的 $v$ 来覆盖 $u$。具体转移看代码。

#include 
#include 
#include 
#include 
#include 
#define re register
#define drep(a,b,c) for(re int a(b) ; a>=(c) ; --a)
#define rep(a,b,c) 	for(re int a(b) ; a<=(c) ; ++a)
using namespace std;
inline int read(){
   
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){
   if(ch == '-') f=-1 ; ch=getchar();}
	while(ch>='0'&&ch<='9'){
   x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
inline void print(int x){
   
	if(x < 0) putchar('-'),x = -x;
	if(x >= 10) print(x / 10);
	putchar(x % 10 + '0');
}
const int M = 3010;
int f[M][3],a[M],head[M];
int n,cnt;
struct edge{
   
	int to,nxt;
}e[M];
inline void add(int u,int v){
   
	e[++cnt].to = v;
	e[cnt].nxt = head[u];
	head[u] = cnt;
}
inline void dfs(int u,int fa){
   
	int fl = 0,mi = 1e9;
	f[u][0] = 0,f[u][1] = a[u],f[u][2] = 0;
	for(re int i(head[u]) ; i ; i=e[i].nxt){
   
		int v = e[i].to;
		if(v == fa) continue;
		dfs(v,u);
		f[u][0] += min(f[v][1],f[v][2]);
		f[u][1] += min(f[v][0],min(f[v][1],f[v][2]));
		if(f[v][1] < f[v]
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