传送门:牛客

题目描述:

John想让他的所有牛用上手机以便相互交流，他需要建立几座信号塔在N块草地中。已知与信号塔相邻的草地
能收到信号。给你N-1个草地(A，B)的相邻关系，问：最少需要建多少个信号塔能实现所有草地都有信号。
输入:
5
1 3
5 2
4 3
3 5
输出:
2

经典的树形dp的题目.与这道战略游戏类似

做这道之前可以先去做那道战略游戏

主要思路:

1. 首先这道题与那道战略游戏最大的不同就是那道题是覆盖树的边,而这道题是覆盖树的结点.注意,这两个问题是不一样的,比如这样的一颗树

1->2->3->4
如果只是为了覆盖结点的话我们可以选择2,3或者1,4,但是如果覆盖边的话我们就不能选择1,4这种情况了

2. 所以我们需要使用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