一般的解版本为
定义两个状态 f[ i ] [ 0 ] 代表该点不选，f[ i ] [ 1 ] 代表该点选，
所以可以得到状态转移方程：
f[u][1] = sum{ min{f[v][0], f[v][1]}, v是u的子结点 }
f[u][0] = sum{ f[v][1], v是u的子结点 }
但自己当时认为0的子节点都选中这样不应该构成最优(该解法原理未知)；
#include <cstdio>
#include <vector>
#include <cmath>
#include <iostream>
#include <cstring>
using namespace std;
#define INF 200000000
typedef long long LL;
const int maxn = 1510;
int d[maxn][2],n;
vector<int> son[maxn];
bool vis[maxn][2];
int dp(int i,int j,int fa){
if(vis[i][j]) return d[i][j];
vis[i][j] = true;
if(son[i].size()==1&&son[i][0]==fa){
return d[i][j]=0;
}
d[i][j]=0;
for(int k=0;k<son[i].size();k++)if(son[i][k]!=fa){
if(j==0) d[i][j]+=dp(son[i][k],1,i)+1;
if(j==1) d[i][j]+=min(dp(son[i][k],0,i),dp(son[i][k],1,i)+1);
}
return d[i][j];
}
int main()
{
while(scanf("%d",&n)==1){
for(int i=0;i<n;i++) son[i].clear();
int fir;
for(int i=1;i<=n;i++){
int x,y,z;
scanf("%d:(%d)",&x,&y);
if(i==1) fir = x;
for(int j=1;j<=y;j++){
scanf("%d",&z);
son[x].push_back(z);
son[z].push_back(x);
}
}
memset(vis,false,sizeof(vis));
int res =min(dp(0,1,-1)+1,dp(0,0,-1));
printf("%d\n",res);
}
return 0;
}
下面是自己写的版本，定义
f[ i ] [ 0 ] 为该节点选中；
f[ i ] [ 1 ] 为该节点未选并且父节点也未选；
f[ i ] [ 2 ] 为该节点未但父节点也选中；状态转移见代码 （但是一直wrong answer ，原因待查，希望大家帮忙）
#include <cstdio>
#include <vector>
#include <cmath>
#include <iostream>
#include <cstring>
using namespace std;
#define INF 200000000
typedef long long LL;
const int maxn = 1510;
int d[maxn][3],n;
vector<int> son[maxn];
bool vis[maxn][3];
int dp(int i,int j,int fa){
if(vis[i][j]) return d[i][j];
vis[i][j] = true;
if(son[i].size()==1&&son[i][0]==fa){
if(j==1) return d[i][j]=maxn*100;
return d[i][j] = 0;
}
d[i][j]=0;
if(j==0){
for(int k=0;k<son[i].size();k++)if(son[i][k]!=fa)
d[i][j]+=min(dp(son[i][k],0,i)+1,dp(son[i][k],2,i));
}
else if(j==2){
for(int k=0;k<son[i].size();k++)if(son[i][k]!=fa)
d[i][j]+=min(dp(son[i][k],0,i)+1,dp(son[i][k],1,i));
}
else {
//if(i==0) cout<<"**\n";
d[i][j]=maxn;
for(int k=0;k<son[i].size();k++)if(son[i][k]!=fa){
int key = son[i][k];
int temp=0;
temp+=dp(key,0,i)+1;
for(int p=0;p<son[i].size();p++)if(son[i][p]!=key&&son[i][p]!=fa){
temp+=min(dp(son[i][p],1,i),dp(son[i][p],0,i)+1);
}
d[i][j]=min(d[i][j],temp);
}
}
return d[i][j];
}
int main()
{
while(scanf("%d",&n)==1){
for(int i=0;i<n;i++) son[i].clear();
int fir;
for(int i=1;i<=n;i++){
int x,y,z;
scanf("%d:(%d)",&x,&y);
if(i==1) fir = x;
for(int j=1;j<=y;j++){
scanf("%d",&z);
son[x].push_back(z);
son[z].push_back(x);
}
}
memset(vis,false,sizeof(vis));
//cout<<dp(fir,0,-1)+1<<dp(fir,1,-1)<<endl;
int res = min(dp(fir,0,-1)+1,dp(fir,1,-1));
if(n==1) res=0;
printf("%d\n",res);
}
return 0;
}