牛客-战略游戏（树上dp）

题目描述

给你一棵树，问你选择最少的点覆盖所有的边

题解：

这个题我一上来直接一发贪心wa掉，后来自我否定了一波

Code

int n,d[maxn],dp[maxn][2],root;
vector<int>e[maxn];
void dfs(int u) {
  for(int v:e[u]) {
    dfs(v);
    dp[u][0]+=dp[v][1];
    dp[u][1]+=min(dp[v][0],dp[v][1]);
  }

}
int  main() {
  n=read();
  rep(i,1,n) dp[i][1]=1;
  for(int i=1 ; i<=n ; i++) {
    int x=read();
    x++;
    int y=read();
    for(int j=1 ; j<=y; j++) {
      int v=read();
      v++;
      e[x].push_back(v);
      d[v]++;
    }
  }
  rep(i,1,n) if(d[i]==0) root=i;
  dfs(root);
  out(min(dp[root][1],dp[root][0]));
  return 0;
}