POJ 3659 Cell Phone Network（树形dp树的最小点支配集）

题意：有N个点，N-1条边，任意两点可达，由此形成了一棵树。选取一个点a，它可覆盖自己以及与自己相邻的点，选取尽量少的点a，使得树中所有点都被覆盖，即求树的最小点支配集。

分析：

1、对于每一个点cur，要想使其被覆盖，有三种情况：

dp[cur][0]---在该点建立塔

dp[cur][1]---在该点的子结点建立塔

dp[cur][2]---在该点的父结点建立塔

2、对于点cur的子结点x，要使其被覆盖：

(1)dp[cur][0] += Min(Min(dp[x][0], dp[x][1]), dp[x][2]);

在cur处建塔的情况下，x可建塔，x的子节点可建塔，x的父结点即cur建塔，三者取最小值，并累加。

(2)dp[cur][2] += Min(dp[x][0], dp[x][1]);

在cur的父结点建塔的情况下，x可建塔，x的子结点可建塔，两者取最小值，并累加。

(3)dp[cur][1] += Min(dp[x][0], dp[x][1]);

在cur的子结点建塔的情况下，至少需要cur的一个子结点建塔cur才能被覆盖，所以对于每一个子结点x，x可建塔，x的子结点可建塔，两者取最小值

与此同时，记录在取最小值的情况下，cur是否有能建塔的子结点，若没有，需要将cur的一个子结点变成可建塔，选取abs(dp[x][1] - dp[x][0])最小的子结点x改变即可。

3、dp[cur][0]最后要加1，因为在cur点要建塔。

#pragma comment(linker, "/STACK:102400000, 102400000")
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<iostream>
#include<sstream>
#include<iterator>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<deque>
#include<queue>
#include<list>
#define Min(a, b) ((a < b) ? a : b)
#define Max(a, b) ((a < b) ? b : a)
const double eps = 1e-8;
inline int dcmp(double a, double b){
    if(fabs(a - b) < eps) return 0;
    return a > b ? 1 : -1;
}
typedef long long LL;
typedef unsigned long long ULL;
const int INT_INF = 0x3f3f3f3f;
const int INT_M_INF = 0x7f7f7f7f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;
const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};
const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};
const int MOD = 1e9 + 7;
const double pi = acos(-1.0);
const int MAXN = 10000 + 10;
const int MAXT = 10000 + 10;
using namespace std;
int N;
vector<int> v[MAXN];
int dp[MAXN][5];
void dfs(int cur, int father){
    memset(dp[cur], 0, sizeof dp[cur]);
    int len = v[cur].size();
    int dif = INT_INF;
    bool ok = false;
    for(int i = 0; i < len; ++i){
        int x = v[cur][i];
        if(x == father) continue;
        if(dp[x][0] == INT_INF) dfs(x, cur);
        dp[cur][0] += Min(Min(dp[x][0], dp[x][1]), dp[x][2]);
        dp[cur][2] += Min(dp[x][0], dp[x][1]);
        dif = Min(dif, abs(dp[x][1] - dp[x][0]));
        if(dp[x][0] < dp[x][1]){
            ok = true;
            dp[cur][1] += dp[x][0];
        }
        else{
            dp[cur][1] += dp[x][1];
        }
    }
    ++dp[cur][0];
    if(!ok) dp[cur][1] += dif;
}
int main(){
    scanf("%d", &N);
    for(int i = 0; i < N - 1; ++i){
        int a, b;
        scanf("%d%d", &a, &b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
    memset(dp, INT_INF, sizeof dp);
    dfs(1, -1);
    printf("%d\n", Min(dp[1][0], dp[1][1]));
    return 0;
}