1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <vector>
using namespace std;

const int MAX_K = 500000;

int k, n[MAX_K + 1], p, res = 0;
vector<int> parents[MAX_K + 1], dp[MAX_K + 1];

void fill_dp_with_zeros(){
    for(int i = 1 ; i <= k; i++){
        dp[i].resize(n[i], 0);
    }
}

void normalize_dp(int i){
    for(int j = 0; j < n[i]; j++){
        if (dp[i][j] == 0) {
            dp[i][j] = 1;
        }
    }
}

void calc_dp_for_row(int i){
    for(int j = 0; j < n[i]; j++){
        int val = parents[i][j];
        if (val != 0){
            dp[i-1][val-1] += dp[i][j];
        }
    }
}

int sum_of_dp_row(int i){
    int sum = 0;
    for(int j = 0; j < n[i]; j++){
        sum += dp[i][j];
    }
    return sum;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> k >> n[1];

    for(int i = 2; i <= k; i++){
        cin>>n[i];

        for(int j = 1; j <= n[i]; j++){
            cin >> p;
            parents[i].push_back(p);
        }
    }

    fill_dp_with_zeros();

    for(int i = k; i >= 2; i--){
        normalize_dp(i);
        calc_dp_for_row(i);
    }
    normalize_dp(1);

    for(int i = 1; i <= k; i++){
        res = max(res, sum_of_dp_row(i));
    }

    cout << res << endl;
}