考虑朴素的搜索。对于树上每一个节点，状态只有选或不选。

而很明显：选了当前节点，儿子节点选不选都可以；而假如不选当前节点，就必须选儿子节点.

容易发现，这样产生的搜索树会有大量的重叠。于是考虑记忆化搜索。

使用一个数组d[cur][2]来记录当前节点选 (d[cur][1]) 或不选 (d[cur][0]) 的搜索结果。

最终，时间复杂度为O(n)级别。

下面上代码:

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 using namespace std; 6 const int MAXN = 1500 + 20; 7 const int INF = 0x7f7f7f7f; 8  9 inline int read()10 {11     int x = 0; char ch = getchar();12     while(!isdigit(ch)) ch = getchar();13     while(isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();14     return x;15 }16 17 int N;18 vector
         
           g[MAXN];19 int d[MAXN][2];20 21 inline void clean()22 {23     for(int i = 0; i <= N; i++)24         g[i].clear();25     memset(d, 0x7f, sizeof(d));26 }27 28 int dfs(int cur, bool opt, int fa)29 {30     if(g[cur].size() == 1 && g[cur][0] == fa)31         return opt;32         33     int ans = 0;34     if(!opt)35     {36         for(int i = 0; i < (int) g[cur].size(); i++)37         {38             int v = g[cur][i];39             if(v != fa)40             {41                 if(d[v][true] == INF) d[v][true] = dfs(v, true, cur);42                 ans += d[v][true];43             }44         }45     }46     else47     {48         for(int i = 0; i < (int) g[cur].size(); i++)49         {50             int v = g[cur][i];51             if(v != fa)52             {53                 if(d[v][true] == INF) d[v][true] = dfs(v, true, cur);54                 if(d[v][false] == INF) d[v][false] = dfs(v, false, cur);55                 ans += min(d[v][false], d[v][true]);56             }57         }58         ans++;59     }60     return ans;61 }62 63 inline void solve()64 {65     cout<
          
           >N)72 {73 clean();74 int u, v, c;75 for(int i = 1; i <= N; i++)76 {77 u = read(), c = read();78 for(int j = 1; j <= c; j++)79 {80 v = read();81 g[u].push_back(v);82 g[v].push_back(u);83 }84 }85 solve();86 }87 return 0;88 }