UVALive 2038 Strategic game

       树形dp，求最少放多少个士兵，使得每条边都被每条路都可以被士兵侦查到。即选择最少的点，使得树上任意一条边至少有一个顶点被选中。dp[i][j]， 当j = 0时，表示当点i不放士兵时最少放了多少个士兵，j = 1时，表示放士兵时最少有多少个。注意：两个相邻点都可以选择放士兵。

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<fstream>
#include<sstream>
#include<vector>
#include<string>
#include<bitset>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define FF(i, a, b) for(int i=a; i<b; i++)
#define REP(i, n) for(int i=0; i<n; i++)
#define FD(i, a, b) for(int i=a; i>=b; i--)
#define CLR(a, b) memset(a, b, sizeof(a))
#define debug puts("**debug**")
#define PB push_back
#define LL long long

using namespace std;

const int N = 2222;
int first[N], next[N << 1];
int dp[N][2];
bool vis[N][2];

struct Edgs
{
    int u, v;
}E[N << 1];
int tot;

void Add_edgs(int u, int v)
{
    E[tot].u = u, E[tot].v = v;
    next[tot] = first[u], first[u] = tot ++;
}

int dfs(int u, int f, int flag)//当前节点u， 父节点f， 是否放士兵flag。
{
    int v, i, j;
    if(vis[u][flag]) return dp[u][flag];
    vis[u][flag] = 1;
    dp[u][flag] = flag;
    for(i = first[u]; ~i; i = next[i])
    {
        v = E[i].v;
        if(v != f)
        {
            if(flag)dp[u][flag] += min(dfs(v, u, 1 - flag), dfs(v, u, flag));
            else dp[u][flag] += dfs(v, u, 1 - flag);
        }
    }
    return dp[u][flag];
}

int main()
{
    //freopen("input.txt", "r", stdin);
    int n, u, v, i, j, t, ans;
    while(scanf("%d", &n) != EOF)
    {
        CLR(first, -1);tot = 1;
        for(i = 0; i < n; i ++)
        {
            scanf("%d:(%d)", &u, &t);
            for(j = 0; j < t; j ++)
            {
                scanf("%d", &v);
                Add_edgs(u, v);
                Add_edgs(v, u);
            }
        }
        CLR(vis, 0);
        ans = min(dfs(0, -1, 0), dfs(0, -1, 1));
        printf("%d\n", ans);
    }
    return 0;
}