传送门:牛客
题目描述:
John想让他的所有牛用上手机以便相互交流,他需要建立几座信号塔在N块草地中。已知与信号塔相邻的草地
能收到信号。给你N-1个草地(A,B)的相邻关系,问:最少需要建多少个信号塔能实现所有草地都有信号。
输入:
5
1 3
5 2
4 3
3 5
输出:
2
经典的树形dp的题目.与这道战略游戏类似
做这道之前可以先去做那道战略游戏
主要思路:
- 首先这道题与那道战略游戏最大的不同就是那道题是覆盖树的边,而这道题是覆盖树的结点.注意,这两个问题是不一样的,比如这样的一颗树
1->2->3->4
如果只是为了覆盖结点的话我们可以选择2,3或者1,4,但是如果覆盖边的话我们就不能选择1,4这种情况了
- 所以我们需要使用dp[i][0/1/2]dp[i][0/1/2]dp[i][0/1/2]来记录三种状态(比那道题多一种状态)
dp[i][0]dp[i][0]dp[i][0]代表当前结点放信号塔
dp[i][1]dp[i][1]dp[i][1]代表当前结点不放信号塔,但是它的儿子放信号塔
dp[i][2]dp[i][2]dp[i][2]代表当前结点不放信号塔,但是它的父亲放信号塔,这种情况类似于我之前局的栗子
所以我们可以写出以下转移:
dp[u][0]+=min(dp[v][0],dp[v][1],dp[v][2])dp[u][0]+=min(dp[v][0],dp[v][1],dp[v][2])dp[u][0]+=min(dp[v][0],dp[v][1],dp[v][2])
当前结点放信号塔,那么无论儿子是什么状态都是可以的
dp[u][2]+=min(dp[v][0],dp[v][1])dp[u][2]+=min(dp[v][0],dp[v][1])dp[u][2]+=min(dp[v][0],dp[v][1])
当前结点的父亲放信号塔,自己没有信号塔,所以儿子不能被自己管,但是儿子可以是除被自己管的其他状态
对于dp[u][1]的状态:
因为当前结点需要被自己的一个儿子管就行了,但是我们有很多个儿子,也就是说我们需要选出一个最佳的儿子.那么对于选择随意的一个儿子,我们有以下贡献:
dp[vj][0]+dp[v_j][0]+dp[vj][0]+∑min(dp[vi][0],dp[vi][1])\sum\limits{min(dp[v_i][0],dp[v_i][1])}∑min(dp[vi][0],dp[vi][1]) i不等于j
那么我们随意的选择两个jjj,比较一下他们的关系,化简一下我们的式子,实际上就是比较
dp[vj][0]−min(dp[vj][0],dp[vj][1])dp[v_j][0]-min(dp[v_j][0],dp[v_j][1])dp[vj][0]−min(dp[vj][0],dp[vj][1])的值
下面是具体的代码部分:
#include
#include
#include
#include
#include
#include