題意是這樣，有一個(gè)籃子里放有若干個(gè)石子，每次可以在樹(shù)的一個(gè)葉節(jié)點(diǎn)上放一個(gè)石子，如果一個(gè)節(jié)點(diǎn)的所有兒子都被放上石子，則將其兒子上的所有石子放回到籃子中，在該節(jié)點(diǎn)上放上一個(gè)石子。問(wèn)要使得根節(jié)點(diǎn)上有一個(gè)石子，籃子中開(kāi)始至少有多少個(gè)石子。
這題是基于樹(shù)的一個(gè)貪心，假設(shè)當(dāng)前節(jié)點(diǎn)為i，其兒子節(jié)點(diǎn)k放入1石子至少需要籃子中初始石子的數(shù)量為num[k]，則在當(dāng)前節(jié)點(diǎn)放入一個(gè)石子的策略是先將num[k]最大的子節(jié)點(diǎn)先放置，然后求得k-1+num[k]的最大值即為當(dāng)前節(jié)點(diǎn)的num值（k為第k個(gè)兒子節(jié)點(diǎn)）
代碼如下
1 # include <cstdio>
2 # include <vector>
3 # include <iostream>
4 # include <algorithm>
5 using namespace std;
6 const int N=201;
7 int n;
8 vector<int> g[N];
9 int minnum[N];
10 bool cmp(const int &a,const int &b)
11 {
12 return minnum[a]>minnum[b];
13 }
14 void dfs(int pos)
15 {
16 if(g[pos].empty())
17 minnum[pos]=1;
18 else
19 {
20 for(int i=0;i<g[pos].size();i++)
21 dfs(g[pos][i]);
22 sort(g[pos].begin(),g[pos].end(),cmp);
23 int max=-1;
24 for(int i=0;i<g[pos].size();i++)
25 if(i+minnum[g[pos][i]]>max)
26 max=i+minnum[g[pos][i]];
27 minnum[pos]=max;
28 }
29 }
30 int main()
31 {
32 int testcase;
33 scanf("%d",&testcase);
34 while(testcase--)
35 {
36 scanf("%d",&n);
37 for(int i=1;i<=n;i++)
38 {
39 int num,pos;
40 scanf("%d %d",&pos,&num);
41 g[pos].clear();
42 while(num--)
43 {
44 int t;
45 scanf("%d",&t);
46 g[pos].push_back(t);
47 }
48 }
49 dfs(1);
50 printf("%d\n",minnum[1]);
51 }
52 //system("pause");
53 return 0;
54 }
55