NC24953-Cell Phone Network

NC24953
*题目描述 *
Farmer John has decided to give each of his cows a cell phone in hopes to encourage their social interaction. This, however, requires him to set up cell phone towers on his N (1 ≤ N ≤ 10,000) pastures (conveniently numbered 1..N) so they can all communicate.
Exactly N-1 pairs of pastures are adjacent, and for any two pastures A and B (1 ≤ A ≤ N; 1 ≤ B ≤ N; A ≠ B) there is a sequence of adjacent pastures such that A is the first pasture in the sequence and B is the last. Farmer John can only place cell phone towers in the pastures, and each tower has enough range to provide service to the pasture it is on and all pastures adjacent to the pasture with the cell tower.
Help him determine the minimum number of towers he must install to provide cell phone service to each pasture.

题目大意
大意就是给你一棵树，每个节点可以放一个灯塔，每个灯塔可以照亮所在节点和恰好相邻的节点，为最少放几个节点。树形dp+贪心，最开始的错误思路是dp[x][0],dp[x][1]分别表示在x修建灯塔和不修建灯塔两种情况，然后分别维护，


如果dp[x][0]选择的都是dp[son][0]，那么自己肯定不会被孩子点亮，方案不合法，所以用一个变量记录dp[son][0]和dp[son][1]的差值最小值，如果选择的孩子真的全都不包含灯塔，就选择差值最小的孩子，修改成包含灯塔的即可。
这样就保证了所有方案合法。
然后通过了20%的数据，只能通过20%的数据，堪称完美。

错因就是dp[x][1]其实可以加上孩子不合法的情况，即如果孩子没有灯塔，且孩子也没有被点亮，只要我自己有灯塔就可以了，所以我少考虑一种情况。
好了，按三种情况，重新推一遍就可以了，解释放在注释里了，方案和公式大同小异。
应该不会有人把我上面的解释当正解吧，嘛，懒得改了，溜了溜了

#include <iostream>
#include <vector>
#include <string.h>
using namespace std;
const int inf=1e8,N=2e5+10;
struct edge{
    int to,next,v;
}e[N];
int ans=inf,cnt=0,h[N],dp[N][3];
void add(int x,int y,int v){
    e[cnt].to=y;
    e[cnt].v=v;
    e[cnt].next=h[x];
    h[x]=cnt++;
}
/*
dp[x][0]    自己建立基站 (孩子随便)
dp[x][1]    自己没有基站 被孩子照亮
dp[x][2]    自己没有基站 也没有被孩子照亮


*/
void dfs(int x,int fa){

    dp[x][0]=1;
    int f1=0,d1=inf;
    for(int i=h[x];~i;i=e[i].next){
        int son=e[i].to;
        if(son==fa) continue;
        dfs(son,x);
        dp[x][0]+=min(dp[son][0],min(dp[son][1],dp[son][2]));//孩子随便
        dp[x][1]+=min(dp[son][0],dp[son][1]);//只要有一个孩子有基站就可以，同时因为自己没有灯塔，所以不能用dp[x][2]
        if(dp[son][0]<=dp[son][1]){
            f1=1;
        }
        else{
            d1=min(d1,dp[son][0]-dp[son][1]);
            //维护一个最小差值 方便修正结果
        }

        dp[x][2]+=dp[son][1];//不能用dp[son][2] 否则孩子永远没办法亮
        //不能用dp[son][0] 否则自己就被照亮了
                //所以孩子只有dp[son][1]
    }
    if(!f1){//选择的孩子都是没有基站的 导致自己没亮
        dp[x][1]+=d1; //修正一波
    }


}
int main(){
    ios::sync_with_stdio(0);
    memset(h,-1,sizeof h);
    memset(dp,0,sizeof dp);
    int n;  cin>>n;
    for(int i=1;i<n;i++){
        int x,y; cin>>x>>y;
        add(x,y,1);
        add(y,x,1);
    }

    dfs(1,-1);
//    for(int i=1;i<=n;i++){
//        cout<<"i = "<<i<<"    dp[0]="<<dp[i][0]<<"    dp[1]="<<dp[i][1]<<"    dp[2]="<<dp[i][2]<<endl;
//    }

    cout<<min(dp[1][0],dp[1][1])<<endl;

    return 0;
}