原题

题目大意：

给一棵有\(n\)个点树，要求建造最小数量的基站，使每个点被全部覆盖

思路：

为了基站数最少，每个点必定只被覆盖一次

每个点有三种状态：

1.\(1\)表示这个点已被选择建基站

2.\(0\)表示这个点没有建基站，意味着他的父节点或子节点中有基站

3.\(-1\)表示这个点还未被选择（初始化）

贪心：基站不可以在叶子节点上

因为如果在叶子节点上基站就只可以覆盖父节点，不划算

所以用\(ret\)来记录\(x\)点的子节点的状态：

1.\(ret==1\)：\(x=0\)

2.\(ret==0\)：\(x=1\)

最后每多一个\(x==1\)，\(ans\)++

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=1e1+10;
int n,ans;
vector<int> e[N];
//1：自己建基站    0：儿子建基站   
int dfs(int u, int p){
    int cho=-1;//choice:当前点的选择（放不放天线） 
    for(int y:e[u]){  
        if(y!=p){
            int ret=dfs(y,u);//儿子的状态 
            if(ret==-1)
                cho=1;
            else if(ret==1 && cho!=1)
                cho=0; 
        }
    }
    if(cho==1) ans++;
    return cho;
}
int main(){
    cin>>n;
    for(int i=1; i<n; i++){
        int a, b;
        cin>>a>>b;
        e[a].push_back(b);
        e[b].push_back(a);
    }
    if(dfs(1,0)==-1) ans++;
    cout<<ans<<endl;
    return 0;
}

来源链接：https://www.cnblogs.com/ccgc718/p/18799556