ACM-ICPC Live Archive 2198 Protecting Zonk

本文从WordPress迁移而来, 查看全部WordPress迁移文章

树dp

题意：给一个无根树，有两种保护，a保护的花费是a，放在一个点，可以保护和它相连的所有边，b保护的花费是b，放在一个点，可以保护到2层的边（即从该点出发路径长度为2的边都能保护，保护能力相当于是a的2倍）。目的是保护所有的边，在一些点上放置a和b保护，使得花费最小

思路参考了Yuan神

这题，有些难想，但其实是想到了不敢下手，因为考虑的方面无非就是，每个点要怎么放，以及放了之后会怎样得到什么样的局面

对于一个点u

  1. A[u]：父边和爷边均被覆盖，u下的子树均被覆盖的最小花费
  2. B[u]：父边被覆盖，u下的子树均被覆盖的最小花费
  3. C[u]：父边不一定被覆盖，但u下子树全部被覆盖的最小花费
  4. D[u]：父边不一定被覆盖，u和一些儿子v的边没有被覆盖全，但所有儿子v下面的子树都被覆盖

A[u]，在u点必定放了b保护，所以u下面的子树，怎么放都可以

A[u] = sigma min(A[v],B[v],C[v],D[v]) + b;

B[u]，可以在u点放一个a保护，那么下面的子树都可以选择A,B,C

B[u] = sigma min(A[v], B[v], C[v]) + a;

B[u]，也可以不再u这个放保护，但是至少一有一个儿子放了b保护，即有一个儿子的状态是A[v]，那么选哪个A[v]呢，当然是 delta = min(A[v] - min(A[v], B[v], C[v])); 即选了这个A[v],新增的费用最小B[u] = delta + sigma min(A[v], B[v], C[v]);

C[u]：下面的子树均选A[u],B[u]

C[u] = sigma min(A[u], B[u]);

当如果一个子树选了A[u]，那么其实其他子树也是可以选C[u]的，同样的，我们选一个A[v]的条件就是

delta = min(A[v] - min(A[v], B[v], C[v])); 即选了这个A[v],新增的费用最小C[u] = delta + sigma min(A[v], B[v], C[v]);

D[u]:因为有些儿子边没有被覆盖全，所以u这个点，以及任何一个儿子都不可能选A[u], A[v]

D[u] = sigma min(B[v], C[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
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 10010
#define INF 0x3f3f3f3f
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

int n,tot,a,b,head[N];
struct edge{
	int u,v,next;
}e[2*N];
int A[N],B[N],C[N],D[N];

void add(int u,int v){
	e[tot].u = u; e[tot].v = v;
	e[tot].next = head[u]; head[u] = tot++;
}

void dfs(int u,int fa){
	A[u] = B[u] = C[u] = D[u] = 0;
	int resb1 = 0 , resb2 = 0;
	int resc1 = 0 , resc2 = 0;
	int delta = INF;

	for(int k = head[u]; k != -1 ; k = e[k].next){
		int v = e[k].v;
		if(v == fa) continue;
		dfs(v,u);
		A[u] += min(min(A[v],B[v]) , min(C[v],D[v]));
		resb1 += min(min(A[v],B[v]) , C[v]);
		resb2 += min(min(A[v],B[v]),C[v]);
		resc1 += min(A[v],B[v]);
		resc2 += min(min(A[v],B[v]),C[v]);
		delta = min(delta , A[v] - min(min(A[v],B[v]),C[v]));
		D[u] += min(B[v],C[v]);
	}
	A[u] += b;
	resb1 += a;
	resb2 += delta;
	resc2 += delta;
	B[u] = min(resb1,resb2);
	C[u] = min(resc1,resc2);
}

int main(){
	while(scanf("%d%d%d",&n,&a,&b)!=EOF){
		if(!n && !a && !b) break;
		tot = 0; cl(head,-1);
		for(int i = 1; i < n; i++){
			int u,v;
			scanf("%d%d",&u,&v);
			add(u,v); add(v,u);
		}
		dfs(1,-1);
		printf("%d\n",min(min(A[1],B[1]),C[1]));
	}
	return 0;
}