其他题解只给了转移方程而没有给清楚为什么是这样的 我在这就简要的分享一下自己的想法吧

首先这是一棵树

我们定义 三种状态：

0.我自己不选，我有儿子选

1.我自己不选，我父亲选

2.我自己选

0状态需要建立反悔机制，因为我只需要一个儿子选，

先推导 dp[x][0]=min(dp[v][0],dp[v][2]); 注意：因为当前节点是不选的，所以他儿子是父亲选择的状态不应该列入考核范围内。

这个式子推出来后可能照成的结果是儿子都没选 那我不就凉了 建立反悔，

t=min(t,dp[v][2]-min(dp[v][0],dp[v][2])) 保证一定有一个是儿子选了的，而且如果不本身就有儿子已经选了的状态t会为0

1状态是不选 所以不能接受儿子对他的依赖 所以 dp[x][1]+=min(dp[v][0],dp[v][2])

2状态呢是自己要选 儿子怎样都可以 dp[x][2]+=min(dp[v][0],min(dp[v][1],dp[v][2]))

于是我们就可以开始愉快的写代码了

可能我大家会有一个疑问 如果是叶子节点，不就不能产生儿子选的状态了吗？？

我们建立的反悔机制在进入时给的是极大值，最后会加上去，如果本身就很大，没有更新就加上去了 肯定不会有点选的

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<queue>
#include<stack>
#include<cmath>
#define LL long long
using namespace std;
inline void read(int &x){
    x=0;int f=1;char c=getchar();
    while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();    }
    while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x*=f;
}
struct node{
    int v,nxt;
}e[10010<<1];
int head[10010],tot;
inline void add(int x,int y)
{
    tot++;
    e[tot].v = y;
    e[tot].nxt = head[x];
    head[x] = tot;
}
int dp[10010][3];//0不选 儿子选  1不选 父亲选 2自己选 
inline void dfs(int x,int fa)
{
    dp[x][0]=0;
    dp[x][1]=0;
    dp[x][2]=1;
    int t=99999999;
    for(int i=head[x];i;i=e[i].nxt)
    {
        int v = e[i].v;
        if(v == fa) continue;
        dfs(v,x);
        dp[x][0]+=min(dp[v][0],dp[v][2]);
        t=min(t,dp[v][2]-min(dp[v][0],dp[v][2]));
        dp[x][1]+=min(dp[v][0],dp[v][2]);//父亲选 儿子不是父亲选随便 
        dp[x][2]+=min(dp[v][0],min(dp[v][1],dp[v][2]));//我选 
    }
    dp[x][0]+=t;
} 
int n,m,a,b;
int main()  
{     
    read(n);
    for(int i=1;i<n;i++)
        read(a),read(b),add(a,b),add(b,a);
    dfs(1,0);
    printf("%d",min(dp[1][0],dp[1][2]));
    return 0;
}