#include <bits/stdc++.h>
#define vec vector
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.begin(),x.end()
#define sz(x) (int) x.size()
#define m_p make_pair
#define pw(x) (1LL<<x)
#define fast_ioi ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
auto rng=bind(uniform_int_distribution<int>(1,1000),mt19937(time(0)));
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<int,int> pii;
typedef long double ld;
struct segtree{
vec<int>t,l,r,p;
// void clr
segtree(){
t.pb(0);l.pb(-1);r.pb(-1);p.pb(0);
}
void clr(){
t.clear();l.clear();r.clear();p.clear();
}
void checkl(int v){
if(l[v]==-1){t.pb(0);l.pb(-1);r.pb(-1);p.pb(0);l[v]=sz(t)-1;}
}
void checkr(int v){
if(r[v]==-1){t.pb(0);l.pb(-1);r.pb(-1);p.pb(0);r[v]=sz(t)-1;}
}
void push(int v,int tl,int tr){
if(tl==tr || p[v]==0) return;
checkl(v);checkr(v);
t[l[v]]+=p[v];t[r[v]]+=p[v];
p[l[v]]+=p[v];p[r[v]]+=p[v];
p[v]=0;
}
void pull(int v){
t[v]=max((l[v]==-1?0:t[l[v]]),(r[v]==-1?0:t[r[v]]));
}
void upd(int id,int x,int v,int tl,int tr){
if(tl==tr){
umax(t[v],x);
// cerr<<"HEY "<<t[v]<<endl;
return;
}
int tm=(tl+tr)>>1;push(v,tl,tr);
if(tm>=id){
checkl(v);
upd(id,x,l[v],tl,tm);
}
else{
checkr(v);
upd(id,x,r[v],tm+1,tr);
}
pull(v);
// cerr<<"HEY"<<' '<<v<<' '<<t[v]<<endl;
}
void add(int l1,int r1,int x,int v,int tl,int tr){
if(tl>=l1 && tr<=r1){
t[v]+=x;p[v]+=x;
return;
}
if(tl>r1 || tr<l1) return;
int tm=(tl+tr)>>1;push(v,tl,tr);
checkl(v);checkr(v);
add(l1,r1,x,l[v],tl,tm);add(l1,r1,x,r[v],tm+1,tr);
pull(v);
}
int get(int l1,int r1,int v,int tl,int tr){
if(v==-1) return 0;
if(tl>=l1 && tr<=r1){
// cerr<<"ALO "<<t[v]<<endl;
return t[v];
}
if(tl>r1 || tr<l1) return 0;
int tm=(tl+tr)>>1;push(v,tl,tr);
return max(get(l1,r1,l[v],tl,tm),get(l1,r1,r[v],tm+1,tr));
}
};
const int N=2e5+1;
vec<int> g[N];
segtree* seg[N];
set<int>* h[N];
int d;
//vec<pii> sons[N];
void dfs(int v,int gl){
// sons[v].pb({0,v});
int big=-1;
for(auto &z : g[v]){
dfs(z,gl+1);
if(big==-1 || (int)(*h[z]).size() > (int)(*h[big]).size()) big=z;
}
if(big==-1){
seg[v]=new segtree();
h[v]=new set<int>();
}
else{
seg[v]=seg[big];h[v]=h[big];
}
for(auto &z : g[v]){
if(z==big) continue;
vec<int>vc;
for(auto &z : (*h[z])){
(*h[v]).insert(z);vc.pb(z);
}
int lst=N;
vec<pii>lel;
vec<int>vls(sz(vc));
for(int i=sz(vc)-1;i>=0;i--){
int h=vc[i]-gl;
int j=max(h,d-h);
vls[i]=(*seg[z]).get(h+gl,N-1,0,0,N-1);
// cerr<<"VL "<<vls[i]<<endl;
lel.pb({vc[i],(*seg[v]).get(j+gl,N-1,0,0,N-1)+vls[i]});
// cerr<<"VL "<<lel.back().s<<endl;
}
for(int i=0;i<sz(vc);i++){
if(i){
// cerr<<vls[i]<<' '<<vls[i-1]<<endl;
assert(vls[i]<=vls[i-1]);
}
int h=vc[i]-gl;
int j=d-h;
if(j<h){
int lft=j+gl,rgt=min(h+gl,lst-1);
if(lft<=rgt) (*seg[v]).add(lft,rgt,vls[i],0,0,N-1);
lst=lft;
}
}
for(auto &z : lel) (*seg[v]).upd(z.f,z.s,0,0,N-1);
(*seg[z]).clr();
(*h[z]).clear();
}
// cerr<<"HEY "<<(*seg[v]).get(gl+d,N-1,0,0,N-1)<<endl;
(*seg[v]).upd(gl,(*seg[v]).get(gl+d,N-1,0,0,N-1)+1,0,0,N-1);
(*h[v]).insert(gl);
// for(auto &z : (*h[v])){
// cerr<<"DP "<<v<<' '<<z-gl<<' '<<(*seg[v]).get(z,z,0,0,N-1)<<endl;
// }
}
//int dp[N][N];
//void dfs1(int v){
// for(auto &z : g[v]){
// dfs1(z);
// }
// int n=sz(g[v]);
// vec<vec<int>>pref(n,vec<int>(d+1,0));
// vec<vec<int>>suf(n,vec<int>(d+1,0));
// for(int i=0;i<n;i++){
// int u=g[v][i];
// if(i+1<n){
// for(int j=d;j>=0;j--){
// pref[i+1][j]=pref[i][j]+dp[u][j];
// }
// }
// }
// for(int i=n-1;i>=0;i--){
// int u=g[v][i];
// if(i>0){
// for(int j=d;j>=0;j--){
// suf[i-1][j]=suf[i][j]+dp[u][j];
// }
// }
// }
// for(int m=0;m<=d;m++){
// int mx=0;
// int j=max(m,d-m-2);
// for(int i=0;i<n;i++){
// umax(mx,pref[i][j]+suf[i][j]+dp[g[v][i]][m]);
// }
// dp[v][m+1]=mx;
// }
// for(int i=N-2;i>=0;i--){
// umax(dp[v][i],dp[v][i+1]);
// }
// umax(dp[v][0],dp[v][d]+1);
//}
signed main(){
fast_ioi;
int n=100;d=3;
cin>>n>>d;
bool dbg=0;
for(int i=1;i<n;i++){
int p;p=rng()%i;
if(!dbg) cin>>p;
g[p].pb(i);
if(dbg)cout<<p<<endl;
}
auto solve=[&](){
dfs(0,0);
int ans=(*seg[0]).t[0];
return ans;
};
// auto brute=[&](){
// dfs1(0);
// return dp[0][0];
// };
cout<<solve();
// assert(solve()==brute());
return 0;
}
/*
7 3
0
1
0
1
3
5
0
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
3 ms |
4940 KB |
Output is correct |
5 |
Correct |
3 ms |
4940 KB |
Output is correct |
6 |
Correct |
3 ms |
4940 KB |
Output is correct |
7 |
Correct |
3 ms |
4940 KB |
Output is correct |
8 |
Correct |
3 ms |
4940 KB |
Output is correct |
9 |
Correct |
4 ms |
4940 KB |
Output is correct |
10 |
Correct |
3 ms |
5000 KB |
Output is correct |
11 |
Correct |
3 ms |
5020 KB |
Output is correct |
12 |
Correct |
3 ms |
4940 KB |
Output is correct |
13 |
Correct |
3 ms |
4940 KB |
Output is correct |
14 |
Correct |
4 ms |
4940 KB |
Output is correct |
15 |
Correct |
3 ms |
4940 KB |
Output is correct |
16 |
Correct |
3 ms |
4940 KB |
Output is correct |
17 |
Correct |
3 ms |
4940 KB |
Output is correct |
18 |
Correct |
3 ms |
4940 KB |
Output is correct |
19 |
Correct |
3 ms |
4940 KB |
Output is correct |
20 |
Correct |
3 ms |
4940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
3 ms |
4940 KB |
Output is correct |
5 |
Correct |
3 ms |
4940 KB |
Output is correct |
6 |
Correct |
3 ms |
4940 KB |
Output is correct |
7 |
Correct |
3 ms |
4940 KB |
Output is correct |
8 |
Correct |
3 ms |
4940 KB |
Output is correct |
9 |
Correct |
4 ms |
4940 KB |
Output is correct |
10 |
Correct |
3 ms |
5000 KB |
Output is correct |
11 |
Correct |
3 ms |
5020 KB |
Output is correct |
12 |
Correct |
3 ms |
4940 KB |
Output is correct |
13 |
Correct |
3 ms |
4940 KB |
Output is correct |
14 |
Correct |
4 ms |
4940 KB |
Output is correct |
15 |
Correct |
3 ms |
4940 KB |
Output is correct |
16 |
Correct |
3 ms |
4940 KB |
Output is correct |
17 |
Correct |
3 ms |
4940 KB |
Output is correct |
18 |
Correct |
3 ms |
4940 KB |
Output is correct |
19 |
Correct |
3 ms |
4940 KB |
Output is correct |
20 |
Correct |
3 ms |
4940 KB |
Output is correct |
21 |
Correct |
5 ms |
5836 KB |
Output is correct |
22 |
Correct |
4 ms |
5196 KB |
Output is correct |
23 |
Correct |
4 ms |
5196 KB |
Output is correct |
24 |
Correct |
4 ms |
5196 KB |
Output is correct |
25 |
Correct |
6 ms |
5452 KB |
Output is correct |
26 |
Correct |
5 ms |
5412 KB |
Output is correct |
27 |
Correct |
7 ms |
5452 KB |
Output is correct |
28 |
Correct |
7 ms |
5580 KB |
Output is correct |
29 |
Correct |
7 ms |
5580 KB |
Output is correct |
30 |
Correct |
7 ms |
5536 KB |
Output is correct |
31 |
Correct |
7 ms |
5592 KB |
Output is correct |
32 |
Correct |
9 ms |
6092 KB |
Output is correct |
33 |
Correct |
7 ms |
6024 KB |
Output is correct |
34 |
Correct |
7 ms |
5964 KB |
Output is correct |
35 |
Correct |
7 ms |
6032 KB |
Output is correct |
36 |
Correct |
10 ms |
6036 KB |
Output is correct |
37 |
Correct |
8 ms |
6092 KB |
Output is correct |
38 |
Correct |
7 ms |
6092 KB |
Output is correct |
39 |
Correct |
7 ms |
6052 KB |
Output is correct |
40 |
Correct |
5 ms |
5836 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
3 ms |
4940 KB |
Output is correct |
5 |
Correct |
3 ms |
4940 KB |
Output is correct |
6 |
Correct |
3 ms |
4940 KB |
Output is correct |
7 |
Correct |
3 ms |
4940 KB |
Output is correct |
8 |
Correct |
3 ms |
4940 KB |
Output is correct |
9 |
Correct |
4 ms |
4940 KB |
Output is correct |
10 |
Correct |
3 ms |
5000 KB |
Output is correct |
11 |
Correct |
3 ms |
5020 KB |
Output is correct |
12 |
Correct |
3 ms |
4940 KB |
Output is correct |
13 |
Correct |
3 ms |
4940 KB |
Output is correct |
14 |
Correct |
4 ms |
4940 KB |
Output is correct |
15 |
Correct |
3 ms |
4940 KB |
Output is correct |
16 |
Correct |
3 ms |
4940 KB |
Output is correct |
17 |
Correct |
3 ms |
4940 KB |
Output is correct |
18 |
Correct |
3 ms |
4940 KB |
Output is correct |
19 |
Correct |
3 ms |
4940 KB |
Output is correct |
20 |
Correct |
3 ms |
4940 KB |
Output is correct |
21 |
Correct |
5 ms |
5836 KB |
Output is correct |
22 |
Correct |
4 ms |
5196 KB |
Output is correct |
23 |
Correct |
4 ms |
5196 KB |
Output is correct |
24 |
Correct |
4 ms |
5196 KB |
Output is correct |
25 |
Correct |
6 ms |
5452 KB |
Output is correct |
26 |
Correct |
5 ms |
5412 KB |
Output is correct |
27 |
Correct |
7 ms |
5452 KB |
Output is correct |
28 |
Correct |
7 ms |
5580 KB |
Output is correct |
29 |
Correct |
7 ms |
5580 KB |
Output is correct |
30 |
Correct |
7 ms |
5536 KB |
Output is correct |
31 |
Correct |
7 ms |
5592 KB |
Output is correct |
32 |
Correct |
9 ms |
6092 KB |
Output is correct |
33 |
Correct |
7 ms |
6024 KB |
Output is correct |
34 |
Correct |
7 ms |
5964 KB |
Output is correct |
35 |
Correct |
7 ms |
6032 KB |
Output is correct |
36 |
Correct |
10 ms |
6036 KB |
Output is correct |
37 |
Correct |
8 ms |
6092 KB |
Output is correct |
38 |
Correct |
7 ms |
6092 KB |
Output is correct |
39 |
Correct |
7 ms |
6052 KB |
Output is correct |
40 |
Correct |
5 ms |
5836 KB |
Output is correct |
41 |
Correct |
455 ms |
75712 KB |
Output is correct |
42 |
Correct |
311 ms |
51924 KB |
Output is correct |
43 |
Correct |
256 ms |
45864 KB |
Output is correct |
44 |
Correct |
248 ms |
45876 KB |
Output is correct |
45 |
Correct |
254 ms |
45884 KB |
Output is correct |
46 |
Correct |
611 ms |
92140 KB |
Output is correct |
47 |
Correct |
512 ms |
86796 KB |
Output is correct |
48 |
Correct |
513 ms |
86884 KB |
Output is correct |
49 |
Correct |
509 ms |
86892 KB |
Output is correct |
50 |
Correct |
299 ms |
80296 KB |
Output is correct |
51 |
Correct |
292 ms |
80340 KB |
Output is correct |
52 |
Correct |
287 ms |
80348 KB |
Output is correct |
53 |
Correct |
634 ms |
156356 KB |
Output is correct |
54 |
Correct |
638 ms |
156312 KB |
Output is correct |
55 |
Correct |
600 ms |
156336 KB |
Output is correct |
56 |
Correct |
10 ms |
6604 KB |
Output is correct |
57 |
Correct |
33 ms |
17308 KB |
Output is correct |
58 |
Correct |
168 ms |
63840 KB |
Output is correct |
59 |
Correct |
491 ms |
137768 KB |
Output is correct |
60 |
Correct |
433 ms |
68800 KB |
Output is correct |
61 |
Correct |
444 ms |
68724 KB |
Output is correct |