本题也是这三天来在下写的几篇树形DP之一，但是不知道为什么洛谷上面老是unknown error，。。。直接去了UVa,说我编译错误。。。我在想是不是头文件的原因，于是被逼无奈，交了一道c89的代码。（结果后来还是CE了）
我真他娘是B了狗了。。。
所以，因为测试数据只过了我们学校的OJ(需要注册才可看题)，我会担心有可能代码有问题，欢迎大家杀我祭天指正错误。
题目描述[传送门]
Bob特别喜欢战略游戏，但有时他不能尽快找到最优解，所以他就很伤心。现在他又有一个问题，他必须保卫一个中世纪的城市，这个城市的道路形成了一棵树。他需要在树的节点上放最少的士兵来观察所有的边。你能帮助他么？
例如下图就只需要一个士兵放在1号节点。
输入
输入文件soldier.in中有多组数据，每组数据的第一行N表示点的个数。接下来N行每行格式如下
x:(k) a1 a2 … ak（x为点的编号，k为与其相连的子节点个数，a1, a2, …, ak分别为子节点的编号）
输出
样例输入
4
0:(1) 1
1:(2) 2 3
2:(0)
3:(0)
5
3:(3) 1 4 2
1:(1) 0
2:(0)
0:(0)
4:(0)
样例输出
1
2
提示
0 < N<= 1500, 0
<= x < N
于是这是我写的第三篇关于树形DP的博客。我越来越熟悉这个美妙而不失简洁的算法。。。。然而选课你还是做不来hiahiahia
让我们来简化分析一下：
给定一个无向多叉树，一个节点可以影响和它直接连接的节点，那请问需要至少多少个节点才可以使所有节点都被影响？
动规最重要是定义状态，一个好的状态可以让你的程序写起来更加容易。
在这里我们规定:f[u][0/1]用于表示u号节点放士兵或者不放士兵时的最小士兵数。
那这个时候我们就要想状态转移方程了
要是u节点不放士兵，那必须至少有一条与之相邻的点放了士兵，要是放士兵，则可放可不放，很容易得出f[u][0]=f[u][0]+f[v][1];//v为一个与u相邻的点 f[u][1]=min(f[v][1],f[v][0])
并且在最后不要忘了把f[u][1]给++。
这样状态转移和定义出来了，那么答案就是min(f[root][0],f[root][1]);
下面给出完整代码：
#include<bits/stdc++.h>
namespace Jason{
inline void scan(int &x){
int f=;x=;char s=getchar();
while(s<'' || s>''){if(s=='-') f=-;s=getchar();}
while(s>='' && s<=''){x=x*+s-'';s=getchar();}
x*=f;
}
inline void print(int x){
if(x<){putchar('-');x=-x;}
if(x>)print(x/);char s=x%+'';
putchar(s);
}
struct Edge_B{
int to,dis;
Edge_B* nxt;
Edge_B(int to=-,int dis=-,Edge_B* n=NULL){this->to=to,this->dis=dis,this->nxt=n;}
};
}
using namespace std;
using namespace Jason;
const int maxn=+;
//--------------------
int n,m,cnt=;
struct Edge{
int to,nxt;
}edge[maxn<<];int head[maxn];
int f[maxn][];
//--------------------
void add(int x,int y)
{
edge[++cnt].nxt=head[x];
edge[cnt].to=y;
head[x]=cnt;
} void dp(int u,int fa)
{
for(int i=head[u];i!=-;i=edge[i].nxt)
{
int v=edge[i].to;
if(v==fa) continue;
dp(v,u);
f[u][]+=f[v][];
f[u][]+=min(f[v][],f[v][]);
}
f[u][]++;
} int main()
{
//freopen("in","r",stdin);
int a,b,c;
while(scanf("%d",&n)==)
{
memset(head,-,sizeof(head));
memset(f,,sizeof(f));
for(int i=;i<n;++i)
{
scanf("%d:(%d)",&a,&b);
for(int i=;i<b;++i) scanf("%d",&c),add(a,c),add(c,a);
}
dp(,-);
print(min(f[][],f[][]));putchar('\n');
}
return ;
}
然而我还是不会选课。。。。。