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
#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define int long long
#define ld long double
#define pb push_back

using namespace std;
#define rg ranges

constexpr int maxN = 500007;
vector<int> repL, isLeaf;

int32_t main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int m, n;
    cin >> m >> n;
    repL.reserve(maxN);
    isLeaf.reserve(maxN);
    repL.resize(n);
    isLeaf.resize(n, 1);
    vector<int> cntLeafs(m), cntRoots(m);
    int bef = 0, prN = n;
    rep(i, 1, m) {
        cin >> n;
        bef += prN;
        repL.resize(bef + n, i);
        isLeaf.resize(bef + n, 1);
        rep(j, 0, n) {
            int x;
            cin >> x;
            if(!x) repL[j + bef] = i;
            else {
                DC << j + bef << ' ' << bef - prN + x - 1 << '\n';
                repL[j + bef] = repL[bef - prN + x - 1], isLeaf[bef - prN + x - 1] = 0;
            }
        }
        rep(j, 0, prN) if(isLeaf[bef - j - 1]) cntLeafs[i - 1]++, cntRoots[repL[bef - j - 1]]++;
        prN = n;
    }
    bef += prN;
    rep(j, 0, prN) if(isLeaf[bef - j - 1]) cntLeafs[m - 1]++, cntRoots[repL[bef - j - 1]]++;
    DEBUG {
        DC << "isLeaf: ";
        rep(i, 0, n) DC << isLeaf[i] << ' ';
        DC << eol;
        DC << "repL:   ";
        rep(i, 0, n) DC << repL[i] << ' ';
        DC << eol;

        DC << "cntLeafs: ";
        rep(i, 0, m) DC << cntLeafs[i] << ' ';
        DC << eol;
        DC << "cntRoots: ";
        rep(i, 0, m) DC << cntRoots[i] << ' ';
        DC << eol;
    }
    int open = 0;
    int ans = 0;
    repD(i, m - 1, -1) {
        open += cntLeafs[i];
        ans = max(ans, open);
        DC << open << '\n';
        open -= cntRoots[i];
    }
    DC << '\n';
    cout << ans << '\n';
}