#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debug_with_space(x) cerr << #x << " " << x << " "
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;
typedef tree <ll, null_type, less_equal <ll>, rb_tree_tag, tree_order_statistics_node_update> OST;
const ll NMAX = 200001;
const ll INF = (1LL << 60);
const ll MOD = 1000000007;
const ll BLOCK = 225;
const ll base = 31;
const ll nr_of_bits = 21;
vector <int> v[NMAX];
ll n, k;
deque <int> dp[NMAX];
int a[NMAX];
int sol = 0;
pii depth[NMAX];
void DFS(int node, int p) {
int DeepSon = 0, zero = 1;
vector <int> maxim;
for(auto x : v[node]) {
if(x == p)
continue;
DFS(x, node);
if(k - 1 <= depth[x].first)
zero += dp[x][k - 1];
int a = depth[x].first + 1;
int b = depth[x].second + (v[x].size() > 2);
if(v[x].size() <= 2){
b = -1;
}
if(depth[node].first < a) {
swap(depth[node].first, depth[node].second);
depth[node].first = a;
DeepSon = x;
} else if(depth[node].second < a) {
depth[node].second = a;
}
if(depth[node].second < b) {
depth[node].second = b;
}
}
int d;
if(v[node].size() == 1 && node != 1) {
dp[node].push_front(1);
return;
}
maxim.resize(depth[node].second + 5, 0);
for(auto x : v[node]) {
if(x == p)
continue;
for(int d = 1; d + d <= k && d <= min(depth[x].first + 1, depth[node].second); d++) {
int c = 0;
if(k - d - 1 <= depth[x].first)
c = dp[x][k - d - 1];
maxim[d] = max(maxim[d], dp[x][d - 1] - c);
}
}
//debug(dp[2][1]);
swap(dp[node], dp[DeepSon]);
dp[node].push_front(zero);
//debug_with_space(node);
//debug(DeepSon);
//debug(dp[node][2]);
for(auto x : v[node]) {
if(x == p || x == DeepSon)
continue;
for(int d = 0; d <= min(depth[x].first, k - 1); d++) {
dp[node][d + 1] += dp[x][d];
}
}
for(int d = 1; d + d <= k && d <= depth[node].second; d++) {
int c = 0;
if(depth[node].first >= k - d) {
c = dp[node][k - d];
}
dp[node][d] = maxim[d] + c;
}
for(int d = depth[node].second; d >= 0; d--) {
if(d + 1 <= depth[node].first)
dp[node][d] = max(dp[node][d], dp[node][d + 1]);
}
}
int main() {
int i, x;
cin >> n >> k;
for(i = 2; i <= n; i++) {
cin >> x;
v[x + 1].push_back(i);
v[i].push_back(x + 1);
}
DFS(1, 0);
cout << dp[1][0];
return 0;
}
Compilation message
catinatree.cpp: In function 'void DFS(int, int)':
catinatree.cpp:53:9: warning: unused variable 'd' [-Wunused-variable]
53 | int d;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
106 ms |
139628 KB |
Output is correct |
2 |
Correct |
105 ms |
139628 KB |
Output is correct |
3 |
Correct |
105 ms |
139628 KB |
Output is correct |
4 |
Correct |
105 ms |
139628 KB |
Output is correct |
5 |
Correct |
103 ms |
139628 KB |
Output is correct |
6 |
Correct |
104 ms |
139628 KB |
Output is correct |
7 |
Correct |
110 ms |
139628 KB |
Output is correct |
8 |
Correct |
112 ms |
139756 KB |
Output is correct |
9 |
Correct |
103 ms |
139704 KB |
Output is correct |
10 |
Correct |
105 ms |
139756 KB |
Output is correct |
11 |
Correct |
121 ms |
139628 KB |
Output is correct |
12 |
Correct |
105 ms |
139628 KB |
Output is correct |
13 |
Correct |
106 ms |
139628 KB |
Output is correct |
14 |
Correct |
104 ms |
139628 KB |
Output is correct |
15 |
Correct |
105 ms |
139756 KB |
Output is correct |
16 |
Correct |
115 ms |
139756 KB |
Output is correct |
17 |
Correct |
108 ms |
139628 KB |
Output is correct |
18 |
Correct |
120 ms |
139628 KB |
Output is correct |
19 |
Correct |
106 ms |
139628 KB |
Output is correct |
20 |
Correct |
106 ms |
139700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
106 ms |
139628 KB |
Output is correct |
2 |
Correct |
105 ms |
139628 KB |
Output is correct |
3 |
Correct |
105 ms |
139628 KB |
Output is correct |
4 |
Correct |
105 ms |
139628 KB |
Output is correct |
5 |
Correct |
103 ms |
139628 KB |
Output is correct |
6 |
Correct |
104 ms |
139628 KB |
Output is correct |
7 |
Correct |
110 ms |
139628 KB |
Output is correct |
8 |
Correct |
112 ms |
139756 KB |
Output is correct |
9 |
Correct |
103 ms |
139704 KB |
Output is correct |
10 |
Correct |
105 ms |
139756 KB |
Output is correct |
11 |
Correct |
121 ms |
139628 KB |
Output is correct |
12 |
Correct |
105 ms |
139628 KB |
Output is correct |
13 |
Correct |
106 ms |
139628 KB |
Output is correct |
14 |
Correct |
104 ms |
139628 KB |
Output is correct |
15 |
Correct |
105 ms |
139756 KB |
Output is correct |
16 |
Correct |
115 ms |
139756 KB |
Output is correct |
17 |
Correct |
108 ms |
139628 KB |
Output is correct |
18 |
Correct |
120 ms |
139628 KB |
Output is correct |
19 |
Correct |
106 ms |
139628 KB |
Output is correct |
20 |
Correct |
106 ms |
139700 KB |
Output is correct |
21 |
Correct |
110 ms |
140172 KB |
Output is correct |
22 |
Correct |
113 ms |
139756 KB |
Output is correct |
23 |
Correct |
108 ms |
139756 KB |
Output is correct |
24 |
Correct |
113 ms |
139884 KB |
Output is correct |
25 |
Correct |
123 ms |
140012 KB |
Output is correct |
26 |
Correct |
120 ms |
140140 KB |
Output is correct |
27 |
Correct |
125 ms |
140012 KB |
Output is correct |
28 |
Correct |
114 ms |
140140 KB |
Output is correct |
29 |
Correct |
119 ms |
140288 KB |
Output is correct |
30 |
Correct |
125 ms |
140140 KB |
Output is correct |
31 |
Correct |
117 ms |
140140 KB |
Output is correct |
32 |
Correct |
133 ms |
140524 KB |
Output is correct |
33 |
Correct |
138 ms |
140524 KB |
Output is correct |
34 |
Correct |
108 ms |
140396 KB |
Output is correct |
35 |
Correct |
109 ms |
140396 KB |
Output is correct |
36 |
Correct |
135 ms |
140396 KB |
Output is correct |
37 |
Correct |
121 ms |
140404 KB |
Output is correct |
38 |
Correct |
113 ms |
140396 KB |
Output is correct |
39 |
Correct |
114 ms |
140396 KB |
Output is correct |
40 |
Correct |
117 ms |
140012 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
106 ms |
139628 KB |
Output is correct |
2 |
Correct |
105 ms |
139628 KB |
Output is correct |
3 |
Correct |
105 ms |
139628 KB |
Output is correct |
4 |
Correct |
105 ms |
139628 KB |
Output is correct |
5 |
Correct |
103 ms |
139628 KB |
Output is correct |
6 |
Correct |
104 ms |
139628 KB |
Output is correct |
7 |
Correct |
110 ms |
139628 KB |
Output is correct |
8 |
Correct |
112 ms |
139756 KB |
Output is correct |
9 |
Correct |
103 ms |
139704 KB |
Output is correct |
10 |
Correct |
105 ms |
139756 KB |
Output is correct |
11 |
Correct |
121 ms |
139628 KB |
Output is correct |
12 |
Correct |
105 ms |
139628 KB |
Output is correct |
13 |
Correct |
106 ms |
139628 KB |
Output is correct |
14 |
Correct |
104 ms |
139628 KB |
Output is correct |
15 |
Correct |
105 ms |
139756 KB |
Output is correct |
16 |
Correct |
115 ms |
139756 KB |
Output is correct |
17 |
Correct |
108 ms |
139628 KB |
Output is correct |
18 |
Correct |
120 ms |
139628 KB |
Output is correct |
19 |
Correct |
106 ms |
139628 KB |
Output is correct |
20 |
Correct |
106 ms |
139700 KB |
Output is correct |
21 |
Correct |
110 ms |
140172 KB |
Output is correct |
22 |
Correct |
113 ms |
139756 KB |
Output is correct |
23 |
Correct |
108 ms |
139756 KB |
Output is correct |
24 |
Correct |
113 ms |
139884 KB |
Output is correct |
25 |
Correct |
123 ms |
140012 KB |
Output is correct |
26 |
Correct |
120 ms |
140140 KB |
Output is correct |
27 |
Correct |
125 ms |
140012 KB |
Output is correct |
28 |
Correct |
114 ms |
140140 KB |
Output is correct |
29 |
Correct |
119 ms |
140288 KB |
Output is correct |
30 |
Correct |
125 ms |
140140 KB |
Output is correct |
31 |
Correct |
117 ms |
140140 KB |
Output is correct |
32 |
Correct |
133 ms |
140524 KB |
Output is correct |
33 |
Correct |
138 ms |
140524 KB |
Output is correct |
34 |
Correct |
108 ms |
140396 KB |
Output is correct |
35 |
Correct |
109 ms |
140396 KB |
Output is correct |
36 |
Correct |
135 ms |
140396 KB |
Output is correct |
37 |
Correct |
121 ms |
140404 KB |
Output is correct |
38 |
Correct |
113 ms |
140396 KB |
Output is correct |
39 |
Correct |
114 ms |
140396 KB |
Output is correct |
40 |
Correct |
117 ms |
140012 KB |
Output is correct |
41 |
Correct |
314 ms |
188584 KB |
Output is correct |
42 |
Correct |
295 ms |
170860 KB |
Output is correct |
43 |
Correct |
279 ms |
170860 KB |
Output is correct |
44 |
Correct |
278 ms |
170748 KB |
Output is correct |
45 |
Correct |
288 ms |
170836 KB |
Output is correct |
46 |
Correct |
495 ms |
202172 KB |
Output is correct |
47 |
Correct |
496 ms |
202092 KB |
Output is correct |
48 |
Correct |
461 ms |
202220 KB |
Output is correct |
49 |
Correct |
466 ms |
202148 KB |
Output is correct |
50 |
Correct |
253 ms |
194956 KB |
Output is correct |
51 |
Correct |
264 ms |
194932 KB |
Output is correct |
52 |
Correct |
245 ms |
194924 KB |
Output is correct |
53 |
Correct |
385 ms |
250544 KB |
Output is correct |
54 |
Correct |
380 ms |
250604 KB |
Output is correct |
55 |
Correct |
387 ms |
250732 KB |
Output is correct |
56 |
Correct |
165 ms |
140652 KB |
Output is correct |
57 |
Correct |
132 ms |
144620 KB |
Output is correct |
58 |
Correct |
193 ms |
164460 KB |
Output is correct |
59 |
Correct |
368 ms |
216684 KB |
Output is correct |
60 |
Correct |
331 ms |
183448 KB |
Output is correct |
61 |
Correct |
378 ms |
182596 KB |
Output is correct |