Cell Phone Network

Description

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.

Input

* Line 1: A single integer: N
* Lines 2..N: Each line specifies a pair of adjacent pastures with two space-separated integers: A and B

Output

* Line 1: A single integer indicating the minimum number of towers to install

Sample Input

5
1 3
5 2
4 3
3 5

Sample Output

2
题意：农民的n个地方需要建电话亭，A有电话，则A相邻的点可以要电话亭也可以不需要电话亭。
分析：最少点覆盖。
分三种情况：
dp[u][0]u建个亭
dp[u][1]u不建亭，不依赖父节点，但u的孩子必须有一个有亭
dp[u][2]u不建亭，依赖于父节点（只要父节点能建个亭）。
代码：
#include <stdio.h>
#include <stdlib.h> 
#define inf (1 << 29)
#define Min(a, b) (a) < (b) ? (a) : (b)
#define maxn 21000
struct T
{
    int v, next;
}fn[maxn];
int th;
int g[maxn], dp[maxn][3], degree[maxn];
void add(int u, int v)
{
    fn[th].v = v, fn[th].next = g[u], g[u] = th++;
}
void dfs(int u, int f)
{
    if (u != 1 && degree[u] == 1)
    {
        dp[u][0] = 1;
        dp[u][1] = inf;
        dp[u][2] = 0;
        return;
    }
    dp[u][0] = 1;
    int i, v, sign, min, del;
    for (i = g[u], sign = 0, min = inf; i != -1; i = fn[i].next)
    {
         v = fn[i].v;
        if (v == f)
        {
            continue;
        }
        dfs(v, u);    
        //如果取u，则孩子v取MIN(的可取[v被自己覆盖]，依赖孩子的孩子[表示v不用已经被覆盖，不依赖u]，依赖父节点u[因为父节点现在取了])
        dp[u][0] += Min(Min(dp[v][0], dp[v][1]), dp[v][2]);
        if (dp[v][0] <= dp[v][1])//u不取也不依赖于父节点，则u依赖于孩子，保证一个孩子被取。
        {
            dp[u][1] += dp[v][0];
            sign = 1;//选了一个有电话的，标志1
        }
        else//选了一个孩子没电话的，要保存min，如果sign没标志过，就得利用有电话的最小值得那个人。
        {
            dp[u][1] += dp[v][1];
            if (min > dp[v][0])
            {
                min = dp[v][0];
                del = dp[v][1];
            }
        }
        dp[u][2] += Min(dp[v][0], dp[v][1]);//u不取，则u依赖于父节点，则取v不依赖与u的最优情况
    }
    if (!sign)
    {
        dp[u][1] += min - del;
    }
}
int main()
{
    int n, u, v, i, j;
    while (scanf("%d", &n) - EOF)
    {
        th = 0;
        for (i = 0; i <= n; i++)
        {
            degree[i] = 0;
            g[i] = -1;
            dp[i][0] = dp[i][1] = dp[i][2] = 0;
        }
        for (i = 1; i < n; i++)
        {
            scanf("%d%d", &u, &v);
            add(u, v);
            add(v, u);
            degree[u]++;
            degree[v]++;
        }
        if (n == 1)
        {
            printf("0\n");
            continue;
        }
        dfs(1, 0);
        printf("%d\n", Min(dp[1][0], dp[1][1]));
    }
    return 0;
}