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;
}