链接：

题意：

求一棵树的最小点覆盖

题解：

dp[i][0]、dp[i][1]分别表示不在i结点上和在i结点上放置士兵时整个以i结点为根的子树被覆盖用到用到目标的最少数量

状态转移：

对叶子结点，有dp[i][0]=0,dp[i][1]=1　　（也是递归的出口）

对非叶子结点，有

dp[i][0]=∑(dp[i][1])

dp[i][1]=∑(min(dp[j][0],dp[j][1]))+1　　（j为i的子结点）

代码：

31 int a[MAXN];32 int dp[MAXN][2];33 VI G[MAXN];34 35 void DP(int u) {36     int dp0 = 0, dp1 = 0;37     if (G[u].size() == 0) {38         dp[u][1] = 1;39         dp[u][0] = 0;40         return;41     }42     rep(i, 0, G[u].size()) {43         int v = G[u][i];44         DP(v);45         dp1 += min(dp[v][1], dp[v][0]);46         dp0 += dp[v][1];47     }48     dp[u][1] = dp1 + 1;49     dp[u][0] = dp0;50 }51 52 int main() {53     int n;54     while (cin >> n) {55         memset(dp, 0, sizeof(dp));56         rep(i, 0, MAXN) G[i].clear();57         int root = -1;58         rep(i, 0, n) {59             int u, m;60             scanf("%d:(%d)", &u, &m);61             if (root == -1) root = u;62             while (m--) {63                 int v;64                 scanf("%d", &v);65                 G[u].pb(v);66                 if (v == root) root = u;67             }68         }69         DP(root);70         cout << min(dp[root][0], dp[root][1]) << endl;71     }72     return 0;73 }