学步园

树形DP

题意： 给定一棵树，选择尽量少的节点，使得每个没有选中的节点至少和一个已选节点相邻。

解法： 关于树形DP，题目通常给的是无根树，那么随便选择一个节点当做根好了，这不影响解题。题目的限制是，如果一个节点没被选中，那么和它相邻的节点至少选一个，若一个节点已选，那么和它相邻的节点选或不选都可以。那么，在树中的体现是，对于一个非根节点，他的限制来自于它的父亲(对于根我们不设限制)，若它的父亲没被选，则它必须被选，若选了它的父亲，则它选或不选都可以。

设状态dp[u][0]为以u为根的子树当u不选时的最小值，dp[u][1]为选了u的最小值。那么有如下转移：

dp[u][0] = sigma(dp[v][1]) v为u在树中的儿子。

dp[u][1] = sigma(max(dp[v][1],dp[v][0]))。

/* **********************************************
Author      : Nero
Created Time: 2013-8-26 12:19:21
Problem id  : LA 2038
Problem Name: Strategic game
 *********************************************** */

/*

树形DP，题目不难，但是唯一的巨大的坑是，书上描述n=0为结束标志，但是网页上的题目没有这一句，所以轻信者得RE。

*/

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define REP(i,a,b) for(int i=(a); i<(int)(b); i++)
#define clr(a,b) memset(a,b,sizeof(a))

const int MAXN = 1510;
struct Edge {
    int v,next;
}g[MAXN<<1];
int head[MAXN],tot;
int dp[MAXN][2];
int mark[MAXN];

void add_edge(int u, int v) {
    g[tot].v = v;
    g[tot].next = head[u];
    head[u] = tot ++;
}

int dfs(int u, int fa, int x) {
    if(!mark[u]) {
        dp[u][0] = 0;
        dp[u][1] = 1;
        for(int p = head[u]; p != -1; p=g[p].next) {
            int v = g[p].v;
            if(v == fa) continue;
            dp[u][0] += dfs(v,u,0);
            dp[u][1] += dfs(v,u,1);
        }
        mark[u] = 1;
    }
    if(x == 1) return min(dp[u][0],dp[u][1]);
    else return dp[u][1];
}

int main() {
    int n;
    while(~scanf("%d", &n)) {
        clr(head, -1);
        clr(mark,0);
        tot = 0;
        int m,a,u;
        REP(i,0,n) {
            scanf("%d", &u);
            scanf(":(%d)", &m);
            while(m--) {
                scanf("%d", &a);
                add_edge(u,a);
                add_edge(a,u);
            }
        }
        printf("%d\n", dfs(0,-1,1));
    }
    return 0;
}