#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 = 300001;
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) {
dp[node].push_front(1);
return;
} maxim.resize(depth[node].second + 1, 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 - 2); 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:39:15: error: invalid use of member function 'std::vector<_Tp, _Alloc>::size_type std::vector<_Tp, _Alloc>::size() const [with _Tp = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::size_type = long unsigned int]' (did you forget the '()' ?)
39 | if(v[x].size <= 2)
| ~~~~~^~~~
| ()
catinatree.cpp:39:7: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
39 | if(v[x].size <= 2)
| ^~
catinatree.cpp:41:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
41 | if(depth[node].first < a) {
| ^~
catinatree.cpp:52:9: warning: unused variable 'd' [-Wunused-variable]
52 | int d;
| ^
