#include <bits/stdc++.h>
using namespace std;
#define mr make_pair
#define endl '\n'
#define F first
#define S second
#define pb push_back
#define all(v) v.begin(), v.end()
#define sz(x) (int) x.size()
//#define int long long
const int N = 2e5 + 10;
const int K = 499;
int dp[N][500], D, ps[N][500];
vector<int> g[N];
unordered_map<int, int> mp[N];
set<int> b[N];
void dfs(int v, int p){
for(int u : g[v]){
if(u == p)
continue;
dfs(u, v);
}
for(int d = D; d > 0; d--){
vector<int> pr, su, V;
pr.pb(0);
su.pb(0);
int x = D - d - 1;
if(x < 0)
continue;
x = max(x, d - 1);
for(int u : g[v]){
if(u == p)
continue;
pr.pb(ps[u][x] + pr.back());
V.pb(u);
}
reverse(all(g[v]));
for(int u : g[v]){
if(u == p)
continue;
su.pb(ps[u][x] + su.back());
}
reverse(all(su));
for(int i = 0; i < sz(pr) - 1; i++){
dp[v][d] = max(dp[v][d], pr[i] + su[i + 1] + dp[V[i]][d - 1]);
}
}
dp[v][0]++;
for(int u : g[v]){
if(u == p)
continue;
dp[v][0] += ps[u][D - 1];
}
for(int i = D; i >= 0; i--)
ps[v][i] = max(ps[v][i + 1], dp[v][i]);
}
void dfs2(int v, int par){
for(int u : g[v]){
if(u == par)
continue;
dfs2(u, v);
}
for(int p = 499; p >= 1; p--){
//cout << p << endl;
int l = 0, r = 200001;
while(r - l > 1){
//cout << l << " " << r << endl;
int d = (l + r) / 2;
vector<int> pr, su, V;
pr.pb(0);
su.pb(0);
int x = D - d - 1;
if(x < 0){
r = d;
continue;
}
x = max(x, d - 1);
for(int u : g[v]){
if(u == par)
continue;
auto it = b[u].lower_bound(x);
if(it == b[u].end())
pr.pb(pr.back());
pr.pb(mp[u][*it] + pr.back());
V.pb(u);
}
reverse(all(g[v]));
for(int u : g[v]){
if(u == par)
continue;
auto it = b[u].lower_bound(x);
if(it == b[u].end())
su.pb(su.back());
su.pb(mp[u][*it] + su.back());
}
reverse(all(su));
int ssb = 0;
for(int i = 0; i < sz(pr) - 1; i++){
auto it = b[V[i]].lower_bound(d - 1);
if(it == b[V[i]].end())
continue;
//cout << "hoora " << V[i] << " " << pr[i] << " " << su[i + 1] << " " << mp[V[i]][*it] << endl;
ssb = max(ssb, pr[i] + su[i + 1] + mp[V[i]][*it]);
}
if(ssb >= p){
dp[v][p] = max(dp[v][p], d);
l = d;
}
else
r = d;
}
}
int ssb = 0;
ssb++;
for(int u : g[v]){
if(u == par)
continue;
ssb += mp[u][D - 1];
}
dp[v][ssb] = max(dp[v][ssb], 0);
for(int i = 499; i >= 0; i--){
mp[v][dp[v][i]] = max(mp[v][dp[v][i]], i);
b[v].insert(dp[v][i]);
}
}
int32_t main(){
ios_base:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
cin >> n >> D;
if(D > n){
cout << 1;
return 0;
}
if(D == 1){
cout << n;
return 0;
}
int p;
for(int i = 1; i < n; i++){
cin >> p;
g[i].pb(p);
g[p].pb(i);
}
if(D < 1){
dfs(0, -1);
cout << ps[0][0];
}
else{
for(int i = 0; i < n; i++){
for(int j = 0; j <= K; j++)
dp[i][j] = -1000000000;
}
dfs2(0, -1);
//cout << "# " << dp[1][1] << endl;
int ans = 1;
for(int i = 1; i <= K; i++){
if(dp[0][i] >= 0)
ans = max(ans, i);
}
cout << ans;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
25360 KB |
Output is correct |
| 2 |
Correct |
19 ms |
25304 KB |
Output is correct |
| 3 |
Correct |
12 ms |
25300 KB |
Output is correct |
| 4 |
Incorrect |
18 ms |
25412 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
25360 KB |
Output is correct |
| 2 |
Correct |
19 ms |
25304 KB |
Output is correct |
| 3 |
Correct |
12 ms |
25300 KB |
Output is correct |
| 4 |
Incorrect |
18 ms |
25412 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
25360 KB |
Output is correct |
| 2 |
Correct |
19 ms |
25304 KB |
Output is correct |
| 3 |
Correct |
12 ms |
25300 KB |
Output is correct |
| 4 |
Incorrect |
18 ms |
25412 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
