Sample A
#include <bits/stdc++.h>
using namespace std;
const int N = 3010;
int n,m,tot;
int f[N][3],fa[N];
int h[N],nxt[N],to[N];
void add(int x,int y) {
to[++tot]=y;
nxt[tot]=h[x];
h[x]=tot;
}
void init() {
int a,b,x;
scanf("%d",&n);
for(int i=1; i<=n; i++) {
scanf("%d %d",&a,&b);
for(int j=1; j<=b; j++) {
scanf("%d",&x);
add(a,x);
fa[x]=a;
}
}
}
void dfs(int u) {
f[u][1]=1;//f[u][1]:以u为根的子树,在u结点放士兵时子树上最小花费
for(int i=h[u]; i; i=nxt[i]) {
int v=to[i];
dfs(v);
f[u][1]+=min(f[v][0],f[v][1]);
f[u][0]+=f[v][1];//f[u][0]:以u为根的子树,不在u结点放士兵时子树上最小花费
}
}
void work() {
int r=0;//注意点编号从0开始
while (fa[r]>0) r++;
dfs(r);
printf("%d\n",min(f[r][0],f[r][1]));
}
int main() {
init();
work();
return 0;
}
Sample B
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int num[2100],f[2100][3],fa[2100];
vector<int> son[2100];
void dfs(int u) {
f[u][1]=1;
for(int i=0; i<son[u].size(); i++) {
int v=son[u][i];
dfs(v);
f[u][0]+=f[v][1];
f[u][1]+=min(f[v][0],f[v][1]);
}
}
int main() {
int n;
scanf("%d",&n);
for(int i=1; i<=n; i++) {
int m;
scanf("%d",&m);
m++;
scanf("%d",&num[m]);
for(int j=1; j<=num[m]; j++) {
int r;
scanf("%d",&r);
son[m].push_back(++r);
fa[r]=m;
}
}
int root=1;
while(fa[root]) root++;
dfs(root);
printf("%d\n",min(f[root][0],f[root][1]));
return 0;
}