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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

    int k;
    cin >> k;

    vector<int> n_day(k);
    cin >> n_day[0];

    vector<vector<int>> par_day(k);
    par_day[0].assign(n_day[0], 0);

    for (int d = 1; d < k; d++) {
        cin >> n_day[d];
        par_day[d].resize(n_day[d]);
        for (int j = 0; j < n_day[d]; j++)
            cin >> par_day[d][j];
    }

    int total = 0;
    for (int d = 0; d < k; d++) total += n_day[d];

    vector<int> day_offset(k + 1, 0);
    for (int d = 0; d < k; d++) day_offset[d + 1] = day_offset[d] + n_day[d];

    vector<int> par(total, 0);
    for (int d = 0; d < k; d++) {
        int base = day_offset[d];
        for (int j = 0; j < n_day[d]; j++)
            par[base + j] = par_day[d][j];
    }
    par_day.clear();

    vector<long long> root_demand(k, 0);
    vector<long long> leaf_supply(k, 0);

    vector<long long> need_cur, need_nxt;

    for (int d = k - 1; d >= 0; d--) {
        int nd = n_day[d];
        need_cur.assign(nd, 0);

        if (d < k - 1) {
            int base_nxt = day_offset[d + 1];
            for (int j2 = 0; j2 < n_day[d + 1]; j2++) {
                int p = par[base_nxt + j2];
                if (p > 0)
                    need_cur[p - 1] += need_nxt[j2];
            }
        }

        long long rd = 0, ls = 0;
        int base = day_offset[d];
        for (int j = 0; j < nd; j++) {
            if (need_cur[j] == 0) {
                need_cur[j] = 1;
                ls++;
            }
            if (par[base + j] == 0)
                rd += need_cur[j];
        }
        root_demand[d] = rd;
        leaf_supply[d] = ls;

        need_nxt.swap(need_cur);
    }

    long long pool = 0, total_workers = 0;
    for (int d = 0; d < k; d++) {
        long long rd = root_demand[d];
        long long reused = min(pool, rd);
        pool -= reused;
        total_workers += rd - reused;
        pool += leaf_supply[d];
    }

    cout << total_workers << "\n";
    return 0;
}