其实好像用不到状态转移方程，不必枚举这个点是否放士兵，取最值。因为，这是一颗有根树，从出度为0的根结点开始往下找，
1.找到某个点的儿子是叶子的话，那这个点一定要放士兵的（贪心，给儿子放的话只能照顾到一条边，给老子的话至少有1条边）；
2.某个点的所有（是所有，不是1个！）儿子都放士兵的话，那父亲就不用放了（照顾到了），否则父亲就一定的放。
  这样搜完，根节点即为所求最小士兵数，有点记忆搜索的问道。
副代码：344ms
#include<iostream>
#include<vector>
#include<string.h>
using namespace std;
vector<int>t[1513];
bool used[1515];
int f[1513]; 
int dp(int root)
{
	int i,j,son;
	int sum=0;
	for(i=0;i<t[root].size();i++)
	{
		son=t[root][i];
		if(t[son].size()==0)
			used[root]=true;
		else  sum+=dp(son);
		
	}
	bool kk=true;
	for(i=0;i<t[root].size();i++)
	  kk=kk&&used[t[root][i]];
		if(kk&&!used[root])
		{
			f[root]=sum;
			used[root]=false;
		}
		else
		{
			f[root]=sum+1;
			used[root]=true;
		}
	return f[root];
}

int main()
{
	int i,j,a,b,n,tmp;
	bool visit[1513]={0};
	while(scanf("%d",&n)!=EOF)
	{
		for(j=1;j<=n;j++)
		{
			  scanf("%d:(%d)",&a,&b);
			for(i=0;i<b;i++)
			{
				scanf("%d",&tmp);
				visit[tmp]=1;
				t[a].push_back(tmp);
			}
	   }
		for(i=0;i<n;i++)
			if(!visit[i])
				break;
		   dp(i);
		   cout<<f[i]<<endl;
		for(i=0;i<n;i++)
			t[i].clear();
		memset(visit,0,sizeof(visit));
		memset(used,0,sizeof(used));
	}
	return 0;
}