原题链接：https://ac.nowcoder.com/acm/problem/24953

题目大意：

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

解题思路：

每一个点有三种状态：
  1.自己覆盖自己
  2.儿子节点覆盖自己
  3.父亲节点覆盖自己
第一种情况找到儿子节点三种状态的最小值。
第三种情况找到儿子节点前两种状态的最小值。
第三种情况需要考虑自己被哪个节点覆盖，首先将他所有儿子节点的前两种状态的最小值相加，同时记录以这种方法有没有取到被儿子节点覆盖的情况，有直接将总和复制给第三种情况，否则取一个差值最小的将这个儿子节点取到在赋值。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
typedef complex <double> cp;
#define debug(a) cout<<#a<<":"<<a<<endl;
#define fr freopen("in.txt","r",stdin);
#define Fill(x,a) memset(x,a,sizeof(x))
#define cpy(a,b) memcpy(a,b,sizeof(a))
const double PI = acos(-1);
const int INF=0x3f3f3f3f;
const int N=1e6+7;
const int mod=1e9+7;
int maxn,minn;
int T,n,m,q;
int head[N];
int cnt;
int dp[N][3];    //0 自身 1 儿子 2 父亲 
struct aa{
    int u,next;
}edge[N];

void init(){
    Fill(head,0);
    cnt=1;
    return ;
}

void add(int u,int v){
    edge[cnt].u=v,edge[cnt].next=head[u];
    head[u]=cnt++;
    return ;
}

void dfs(int u,int p){
    int v,ans=0;
    int a,b,flag;
    flag=INF;
    if(edge[head[u]].next==0&&u!=1){    //叶子节点 
        dp[u][0]=1;
        dp[u][1]=INF;
        dp[u][2]=0;
        return ;
    }
    dp[u][0]=1; 
    for(int i=head[u];i!=0;i=edge[i].next){
        v=edge[i].u;
        if(v==p)    continue;
        dfs(v,u);
        dp[u][0]+=min(dp[v][0],min(dp[v][1],dp[v][2]));
        dp[u][2]+=min(dp[v][1],dp[v][0]);
        ans+=min(dp[v][0],dp[v][1]);
        if(dp[v][0]-dp[v][1]<flag){
            flag=dp[v][0]-dp[v][1];
            a=dp[v][0],b=dp[v][1];
        }
    }
    if(flag>0){
        ans=ans-b+a;
    }
    dp[u][1]=ans;
    return ;
}


int main(){
    int u,v,ans;
    cin>>n;
    init();
    for(int i=1;i<n;i++){
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    dfs(1,0);
    ans=min(dp[1][0],dp[1][1]);
    cout<<ans<<endl;

    return 0;
}