GYM101116K

树上贪心
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int n;
 4 struct node
 5 {
 6     int v;
 7     int ans;
 8     string ss;
 9 }A[1111];
10 vector <int> E[1111];
11 vector <node> dd[1111];
12 map<string,int> M;
13 bool cmp(node a, node b)
14 {
15     return a.ans > b.ans;
16 }
17 void dfs(int u)
18 {
19     dd[u].clear();
20     A[u].ans = max(A[u].ans,1+(int)E[u].size());
21     for (int i = 0; i<E[u].size();i++)
22     {
23         if (A[E[u][i]].ans == 0)
24         dfs(E[u][i]);
25         dd[u].push_back(A[E[u][i]]);
26     }
27     sort(dd[u].begin(),dd[u].end(),cmp);
28     for (int i = 0 ; i<dd[u].size(); i++)
29         A[u].ans = max(A[u].ans,dd[u][i].ans+i);
30     return;
31 }
32 int main()
33 {
34     //freopen("in.txt","r",stdin);
35     int N,u;
36     cin >> N;
37     int tot = 0;
38     for (int i = 1; i<=N; i++)
39     {
40         string s;
41         cin >> s;
42         if (M[s] == 0 ) {
43             M[s] = (++tot);
44             u = tot;
45             A[tot].ss= s;
46         }
47         else u = M[s];
48 
49         int t;
50         cin >> t;
51         for (int k = 1 ; k<=t ;k++)
52         {
53             string ss;
54             cin >> ss;
55             if (ss[0]>='a'&&ss[0]<='z') A[u].v++;
56             else
57             {
58                 if (M[ss]==0) {M[ss]=(++tot);A[tot].ss= ss;}
59                 E[u].push_back(M[ss]);
60             }
61         }
62     }
63 
64     dfs(1);
65     cout << A[1].ans<<endl;
66 }