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
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

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

	vector<int> n(k + 1, 0);
	vector<vector<int>> parent(k + 1);
	n[1] = n1;

	for (int day = 2; day <= k; ++day) {
		int ni;
		cin >> ni;
		n[day] = ni;
		parent[day].assign(ni + 1, 0);
		for (int j = 1; j <= ni; ++j) {
			cin >> parent[day][j];
		}
	}

	vector<long long> need_next(n[k] + 1, 1);
	long long day_sum = static_cast<long long>(n[k]);
	long long answer = day_sum;

	for (int day = k - 1; day >= 1; --day) {
		vector<long long> child_sum(n[day] + 1, 0);

		for (int v = 1; v <= n[day + 1]; ++v) {
			int p = parent[day + 1][v];
			if (p > 0) {
				child_sum[p] += need_next[v];
			}
		}

		vector<long long> need_cur(n[day] + 1, 1);
		day_sum = 0;
		for (int u = 1; u <= n[day]; ++u) {
			need_cur[u] = max(1LL, child_sum[u]);
			day_sum += need_cur[u];
		}

		answer = max(answer, day_sum);
		need_next.swap(need_cur);
	}

	cout << answer << '\n';
	return 0;
}