树形动态规划，士兵

dp.c

#include<iostream>
#include<algorithm>
#include <stdio.h>
using namespace std;

#define COUNT 1501

int father[COUNT];
int childcnt[COUNT];
int n;
int dp[COUNT][2];

void DP(int root)
{
	if (childcnt[root] == 0)
	{
		dp[root][0] = 0;
		dp[root][1] = 1;
		return;
	}

	int dp0=0, dp1=0;

	for (int i = 0; i < n; i++)
	{
		if (father[i] == root)
		{
			DP(i);
			dp0 +=dp[i][1];
			dp1 += min(dp[i][0],dp[i][1]);
		}
	}

	dp[root][0] = dp0;
	dp[root][1] = dp1 + 1;
}

int main()
{
	
	while (scanf("%d",&n)!=EOF)
	{
		memset(father, -1, sizeof(father));
		memset(childcnt, 0, sizeof(childcnt));

		int root = -1;
		for(int i=0;i<n;i++)
		{
			int nodeid, chldcnt;
			scanf("%d:(%d)",&nodeid,&chldcnt);

			childcnt[nodeid] = chldcnt;

			if (root == -1) root = nodeid;

			while (chldcnt--)
			{
				int c;
				scanf("%d", &c);
				father[c] = nodeid;

				if (c == root) root = nodeid;
			}
		}

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