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
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
using ll = long long ;

#define st first 
#define nd second
#define DEBUG 
//
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);

    int k, n1;
    cin >> k >> n1 ;

    vector<vector<int>> A(k);
    vector<int> N(k);
    
    N[0] = n1;
    A[0].assign(n1 + 1, 0); 
    //
    for (int i = 1; i < k; ++i) {
        cin >> N[i];
        A[i].assign(N[i] + 1, 0);
        for (int j = 1; j <= N[i]; ++j) {
            cin >> A[i][j];
        }
    }

    vector<vector<ll>> potrzeba(k);
    for (int i = 0; i < k; ++i)  potrzeba[i].assign(N[i] + 1, 1) ;
    vector<vector<ll>> suma_dzieci(k);
    for (int i = 0; i < k; ++i) {
        suma_dzieci[i].assign(N[i] + 1, 0) ;
    }
    // ile dla danego drzewa
    for (int i = k - 1; i > 0 ; --i) {
        for (int j = 1; j <= N[i]; ++j) {
            int rodzic = A[i][j] ;
            if (rodzic > 0) {
                suma_dzieci[i - 1][rodzic] += potrzeba[i][j];
            }
        }
        for (int j = 1 ; j <= N[i - 1]; ++j) {
            potrzeba[i - 1][j] = max(1LL, suma_dzieci[i - 1][j]);
        }
    }
    ll total = 0 , zapas = 0 ;
    // ilerazem
    for (int i = 0; i < k; ++i) {
        ll potrzebni_dzisiaj = 0;
        
        if (i == 0) {
            for (int j = 1; j <= N[0]; j++) {
                potrzebni_dzisiaj += potrzeba[0][j];
            }
        } 
        else {
            for (int j = 1; j <= N[i]; j++) {
                if (A[i][j] == 0) { /// tylko nowe drzewa
                    potrzebni_dzisiaj += potrzeba[i][j];
                }
            }
        }
        if (zapas >=potrzebni_dzisiaj) {
            zapas -=potrzebni_dzisiaj;
        } else {
            total += ( potrzebni_dzisiaj - zapas);
            zapas = 0;
        }
        for (int j = 1; j <= N[i]; j++) {
            if ( suma_dzieci[i][j] == 0) {
                zapas ++;
            }
        }
    }
    cout  << total ;
    return 0;
}