UVALive 2038 Strategic game--树形dp

原题链接：​​http://vjudge.net/problem/UVALive-2038​​

题意：一棵树，n个点，0为根，求最少的点可以覆盖所有边。

分析：

dp[ u ][ 0 ]表示u点不选；

dp[ u ][ 1 ]表示该点选择。

#define _CRT_SECURE_NO_DEPRECATE 

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<string>
#include<stdio.h>
#define INF 99999999
#define eps 0.0001
using namespace std;

int n;
bool vis[1505];
int dp[1505][2];//dp[u][0]表示u点未选
vector<int> vec[1505];

void tree_dp(int u)
{
  dp[u][0] = 0;
  dp[u][1] = 1;
  vis[u] = 1;
  for (int i = 0; i < vec[u].size(); i++)
  {
    int v = vec[u][i];
    if (vis[v])
      continue;
    tree_dp(v);
    dp[u][0] += dp[v][1];
    dp[u][1] += min(dp[v][0], dp[v][1]);
  }
}

int main() 
{
  while (~scanf("%d", &n))
  {
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i < n; i++)
      vec[i].clear();

    int u, t, v;
    for (int i = 0; i < n; i++)
    {
      scanf("%d:(%d)", &u, &t);
      while (t--)
      {
        scanf("%d", &v);
        vec[u].push_back(v);
        vec[v].push_back(u);
      }
    }

    tree_dp(0);

    printf("%d\n", min(dp[0][0], dp[0][1]));
  }
  return 0;
}