题目描述：

Farmer John决定为他的所有奶牛都配备手机，以此鼓励她们互相交流。
不过，为此FJ必须在奶牛们居住的N(1 <= N <= 10,000)块草地中选一些建上
无线电通讯塔，来保证任意两块草地间都存在手机信号。所有的N块草地按1..N
顺次编号。
    所有草地中只有N-1对是相邻的，不过对任意两块草地A和B(1 <= A <= N; 
1 <= B <= N; A != B)，都可以找到一个以A开头以B结尾的草地序列，并且序列
中相邻的编号所代表的草地相邻。无线电通讯塔只能建在草地上，一座塔的服务
范围为它所在的那块草地，以及与那块草地相邻的所有草地。

    请你帮FJ计算一下，为了建立能覆盖到所有草地的通信系统，他最少要建
多少座无线电通讯塔。

输入：

输入格式:

* 第1行: 1个整数，N

* 第2..N行: 每行为2个用空格隔开的整数A、B，为两块相邻草地的编号

输出：

输出格式:

* 第1行: 输出1个整数，即FJ最少建立无线电通讯塔的数目

输入样例：

5
1 3
5 2
4 3
3 5

输出样例：

2

提示：

输入说明:

    Farmer John的农场中有5块草地：草地1和草地3相邻，草地5和草地2、草地

4和草地3，草地3和草地5也是如此。
输出说明:

FJ可以选择在草地2和草地3，或是草地3和草地5上建通讯塔

思路分析：

为了更好的理解题目，我们先将样例的树所画出。

我们可以这样想：

每一个节点一共分为三种情况，就是f[i][0]~f[i][2]。

一是第i号节点和它的子树都被覆盖，但是i上无塔。

二是第i号节点和它的子树都被覆盖，i上有塔。

三是它的子树都被覆盖。

我们分别用f[i][0]表示第一种情况，f[i][1]表示第二种情况，f[i][2]表示第三种情况。

状态定义完毕，现在我们开始思考状态转移。

那么第一种，因为i上无塔，所以就从它的儿子上取最小值转移（因为有多个，所以是累加）。

那么第三种，因为i的子树被覆盖，所以就是从它的儿子上取第二种情况（f[i][1]）

（因为有多个，所以是累加）。

最后是第二种，就是它与儿子的第一种情况（因为i上有塔）与覆盖子树的最小费用减去子节点的第一和第二种情况的最小值的最小值。

是不是感觉蒙了，结合代码理解吧。

代码实现：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
vector<int>G[10005];
int n,m,f[10005][5];
void dfs(int x,int fa)
{
    f[x][0]=1;
    f[x][1]=10000000;
    int sum=0;
    for(int i=0;i<G[x].size();i++)
    {
        if(fa==G[x][i])
            continue;
        dfs(G[x][i],x);
        f[x][0]+=min(f[G[x][i]][0],min(f[G[x][i]][1],f[G[x][i]][2]));
        sum+=min(f[G[x][i]][1],f[G[x][i]][0]);
        f[x][2]+=f[G[x][i]][1];
    }
    if(G[x].size()==1&&x!=1)
        return;
    for(int i=0;i<G[x].size();i++)
    {
        if(G[x][i]==fa)
            continue;
        f[x][1]=min(f[x][1],f[G[x][i]][0]+sum-min(f[G[x][i]][0],f[G[x][i]][1]));
    }
}
int main()
{
    scanf("%d",&n);
    int a,b;
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&a,&b);
        G[a].push_back(b);
        G[b].push_back(a);
    }
    dfs(1,0);
    printf("%d",min(f[1][1],f[1][0]));
}