#include <bits/stdc++.h>
#define FastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define PB push_back
#define ALL(v) (v).begin(), (v).end()
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define fi first
#define se second
#define BIT(x, i) (((x) >> (i)) & 1)
using namespace std;
/** END OF TEMPLATE **/
const int mxN = 2e5 + 5;
typedef pair<int, int> pii;
int n, k;
vector<int> g[mxN];
int f[mxN], d[mxN];
void dfs(int u, int par) {
f[u] = 1;
vector<int> t{0};
for(int &v : g[u]) {
if(v == par) continue;
dfs(v, u);
t.PB(d[v]);
f[u] += f[v];
}
sort(ALL(t));
int pos = t.size() - 1;
for(int i = 0; i < t.size()-2; ++i)
if(t[i] + t[i+1] < k) f[u]--;
else {
pos = i;
break;
}
d[u] = t[pos] + 1;
}
int main()
{
FastIO;
//freopen(".inp", "r", stdin);
//freopen(".out", "w", stdout);
cin >> n >> k;
FOR(i, 2, n) {
int x; cin >> x;
g[i].PB(x+1); g[x+1].PB(i);
}
dfs(1, 0);
cout << f[1];
return 0;
}
/*
*/
Compilation message
catinatree.cpp: In function 'void dfs(int, int)':
catinatree.cpp:32:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for(int i = 0; i < t.size()-2; ++i)
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
