题面
题目背景
Bob 喜欢玩电脑游戏，特别是战略游戏。但是他经常无法找到快速玩过游戏的办法。现在他有个问题。
题目描述
他要建立一个古城堡，城堡中的路形成一棵无根树。他要在这棵树的结点上放置最少数目的士兵，使得这些士兵能了望到所有的路。
注意，某个士兵在一个结点上时，与该结点相连的所有边将都可以被了望到。
请你编一程序，给定一树，帮 Bob 计算出他需要放置最少的士兵。
输入格式
第一行一个整数(n)，表示树中结点的数目。
第二行至第(n+1) 行，每行描述每个结点信息，依次为：一个整数(i)，代表该结点标号，一个自然数 (k)，代表后面有(k) 条无向边与结点 (i) 相连。接下来 (k) 个整数，分别是每条边的另一个结点标号 (r_1,r_2,cdots,r_k)，表示 (i)与这些点间各有一条无向边相连。
对于一个(n) 个结点的树，结点标号在 (0) 到 (n-1) 之间，在输入数据中每条边只出现一次。保证输入是一棵树。
输出格式
输出文件仅包含一个整数，为所求的最少的士兵数目。
输入输出样例
输入 #1复制
4
0 1 1
1 2 2 3
2 0
3 0
输出 #1复制
1
说明/提示
数据规模与约定
对于全部的测试点，保证 (1 leq n leq 1500)
题解
因为是树形结构，并且因为是求最值的问题，所以我们就想到了用树形(dp)去做这道题
一般以节点的深浅（子树从小到大）的顺序作为(DP)的阶段，(DP)的状态表示中，第一维通常是节点的
编号，(代表以该节点为根的子树)
所以我们设(f[i][0/1])表示该节点放还是不放士兵
根据题意，如果当前的节点不放士兵，那么它的子节点必须全部放置士兵，因为要满足士兵可以看到所
有的边。因此我们有状态转移方程(f[u][0]+=f[v][1])(其中v是u的子节点)
如果当前的节点放置
那么我们可以取最小值(f[u][1]+=min(f[v][0],f[v][1]))
注意：可以选择任意一个节点为根，答案都是一样的
最后我们的答案就是(min(f[选择的节点][1],f[选择的节点][0]))
代码
#include<bits/stdc++.h>
using namespace std;
const int N=50000;
int f[N][2];
int happy[N];
int n;
int din[N];
int ne[N],ver[N],head[N],idx;
void add(int x,int y)
{
ne[idx]=head[x];
ver[idx]=y;
head[x]=idx;
idx++;
}
void dp(int x,int father)
{
f[x][1]=1;
for(int i=head[x];i!=-1;i=ne[i])
{
int y=ver[i];
if(y==father)continue;
dp(y,x);
f[x][0]+=f[y][1];
f[x][1]+=min(f[y][0],f[y][1]);
}
}
int main()
{
memset(head,-1,sizeof(head));
cin>>n;
for(int i=1;i<=n;i++)
{
int a,k;
cin>>a>>k;
for(int i=1;i<=k;i++)
{
int q;
cin>>q;
add(q,a);
add(a,q);
}
}
dp(0,-1);
cout<<min(f[0][0],f[0][1]);
return 0;
}