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 <bits/stdc++.h>
#define f first
#define s second
using namespace std;

struct Wyd {
    int par;
    vector<int> c;
    int siz = 0;
};

vector<Wyd> d[500009];
vector<pair<int, int>> roots;


int main() {
    cin.tie(0)->sync_with_stdio(0);
    long long k, n1;
    cin >> k;
    cin >> n1;
    for (int i = 0; i < n1; i++) {
        d[1].push_back({ -1, {}});
        roots.push_back({1, i});
    }
    for (int i = 2; i <= k; i++) {
        int n;
        cin >> n;
        for (int j = 0; j < n; j++) {
            int a;
            cin >> a;
            d[i].push_back({a - 1, {}});
            if (a) d[i - 1][a - 1].c.push_back(j);
            else roots.push_back({i, j});
        }
    }

    for(int i=500000;i>=1;i--){
        for(auto &j : d[i]){
            if(j.c.size()==0) j.siz++;
            else {
                for(auto c : j.c){
                    j.siz+=d[i+1][c].siz;
                }
            }
        }
    }

    long long wyn = 0;
    long long zos = 0;
    int wr = 0;


    for (int i = 1; i <= k; i++) {
        for (auto j : d[i]) {
            if (j.par == -1) {
                int pot = max(0LL, j.siz - zos);
                wyn += pot;
                zos -= (j.siz - pot);
            }
            if (j.c.size() == 0) wr++;
        }
        zos += wr;
        wr = 0;
    }
    cout << wyn;

}

//41760