本文从WordPress迁移而来, 查看全部WordPress迁移文章
树dp
题意:给一个无根树,有两种保护,a保护的花费是a,放在一个点,可以保护和它相连的所有边,b保护的花费是b,放在一个点,可以保护到2层的边(即从该点出发路径长度为2的边都能保护,保护能力相当于是a的2倍)。目的是保护所有的边,在一些点上放置a和b保护,使得花费最小
思路参考了Yuan神
这题,有些难想,但其实是想到了不敢下手,因为考虑的方面无非就是,每个点要怎么放,以及放了之后会怎样得到什么样的局面
对于一个点u
- A[u]:父边和爷边均被覆盖,u下的子树均被覆盖的最小花费
- B[u]:父边被覆盖,u下的子树均被覆盖的最小花费
- C[u]:父边不一定被覆盖,但u下子树全部被覆盖的最小花费
- 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 |
|