Cell Phone Network 题解

该题是点的最小覆盖集问题。
题意：求覆盖一个树所有的点，需要覆盖最小的次数，覆盖一个点需要耗费一次次数，覆盖完以后，那么相邻的点也被覆盖。

对于无向树，直接随便找一个结点作为根，然后把整棵树支起来，就有了根和叶子！
需要一点想象力，反正无向树怎么旋转都可以。
那么寻找当前点的状态，如果一个树都被覆盖，那么这一个点，肯定要么是自己覆盖的，要么是父亲覆盖的，要么是儿子覆盖的，就找到了三种状态。
状态1：自己覆盖
那么对于自己的儿子而言，可以覆盖也可以不覆盖（求min就好了）
状态2：儿子覆盖
那么只要有至少有一个儿子是自己覆盖了的就好了
状态3：父亲覆盖
那么对于自己的儿子，可以是他本身覆盖，也可以是儿子的儿子覆盖。

对于特殊的点，要特殊考虑，有以下两种情况：
1.当前点没有父亲（根结点），那么该点的状态3不存在
2.当前点没有孩子（叶子结点），那么该点状态2不存在

状态转移方程：
dp[root][0]=1+min(dp[son][0],dp[son][1],dp[son][2])
自己覆盖的时候，孩子们的状态无所谓
如果root点有孩子：
dp[root][1]=min(dp[son][0],dp[son][1])+inc(if(dp[son][0]>dp[son][1])) inc=min(inc,(dp[son][0]>dp[son][1])))
如果root点没有孩子：
dp[root][1]=INF
如果root点有父亲：
dp[root][2]= min(dp[to][0],dp[to][1])
如果root点没有父亲：
dp[root][2]=INF

有了状态转移方程，只要通过dfs搜索的时候把状态转移方程带入即可求解。
以下是代码：

#include <bits/stdc++.h>
using namespace std;
const int N=10100;
const int INF=0x3f3f3f3f;
vector <int> G[N];
int dp[N][3];//0表示该点覆盖 1表示该点儿子覆盖 2表示该点父亲覆盖
void dfs(int root,int pre)
{
    bool haveson=false;
    bool coverson=false;
    int inc=0x3f3f3f3f;
    for(int i=0;i<G[root].size();i++)
    {
        int to=G[root][i];
        if(to==pre) continue;
        haveson=true;
        dfs(to,root);
        dp[root][0]+=min(dp[to][0],min(dp[to][1],dp[to][2]));
        if(root==1) dp[root][2]=INF;
        else dp[root][2]+=min(dp[to][0],dp[to][1]);
        inc=min(inc,dp[to][0]-dp[to][1]);
        if(dp[to][0]<=dp[to][1])
        {
            coverson=true;
            dp[root][1]+=dp[to][0];
        }
        else
        {
            dp[root][1]+=dp[to][1];
        }
    }
    if(!haveson) dp[root][1]=INF;
    else if(!coverson) dp[root][1]+=inc;
    dp[root][0]+=1;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1,0);
    printf("%d\n",min(dp[1][0],min(dp[1][1],dp[1][2])));
}