Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define FOR(i,a,b) for(int i=(a);i<(b);++i)
- #define FORD(i, a, b) for(int i = (a); i >= (b); --i)
- #define VAR(v, i) __typeof(i) v=(i)
- #define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
- #define all(v) (v).begin(),(v).end()
- #define PII pair<int,int>
- #define mp make_pair
- #define st first
- #define nd second
- #define pb push_back
- #define lint long long int
- #define VI vector<int>
- #define debug(x) {cerr <<#x <<" = " <<x <<endl; }
- #define debug2(x,y) {cerr <<#x <<" = " <<x << ", "<<#y<<" = "<< y <<endl; }
- #define debug3(x,y,z) {cerr <<#x <<" = " <<x << ", "<<#y<<" = "<< y << ", " << #z << " = " << z <<endl; }
- #define debugv(x) {{cerr <<#x <<" = "; FORE(itt, (x)) cerr <<*itt <<", "; cerr <<endl; }}
- #define debugt(t,n) {{cerr <<#t <<" = "; FOR(it,0,(n)) cerr <<t[it] <<", "; cerr <<endl; }}
- #define make( x) int (x); scanf("%d",&(x));
- #define make2( x, y) int (x), (y); scanf("%d%d",&(x),&(y));
- #define make3(x, y, z) int (x), (y), (z); scanf("%d%d%d",&(x),&(y),&(z));
- #define make4(x, y, z, t) int (x), (y), (z), (t); scanf("%d%d%d%d",&(x),&(y),&(z),&(t));
- #define makev(v,n) VI (v); FOR(i,0,(n)) { make(a); (v).pb(a);}
- #define IOS ios_base::sync_with_stdio(0)
- #define HEAP priority_queue
- #define read( x) scanf("%d",&(x));
- #define read2( x, y) scanf("%d%d",&(x),&(y));
- #define read3(x, y, z) scanf("%d%d%d",&(x),&(y),&(z));
- #define read4(x, y, z, t) scanf("%d%d%d%d",&(x),&(y),&(z),&(t));
- #define readv(v,n) FOR(i,0,(n)) { make(a); (v).pb(a);}
- #define jeb fflush(stdout)
- using namespace std;
- const int max_n = 2e5+5;
- int n, d;
- int par[max_n];
- VI g[max_n];
- int depth[max_n];
- int zepsute[max_n];
- int val[max_n];
- void dfs(int v, int h) {
- depth[v] = h;
- FORE(i, g[v]) {
- dfs(*i, h+1);
- }
- }
- int main() {
- read2(n, d);
- int ans = 0;
- FOR(i,0,n-1) {
- make(a);
- g[a].pb(i+1);
- par[i+1] = a;
- }
- dfs(0,0);
- if (d == 1) {
- printf("%d\n", n);
- return 0;
- }
- vector<PII> dupa;
- FOR(i,0,n) dupa.pb(mp(depth[i], i));
- sort(all(dupa));
- reverse(all(dupa));
- FOR(i,0,n) zepsute[i] = d;
- FOR(i,0,n) {
- int v = dupa[i].nd;
- if (g[v].size() == 0) {
- val[v] = 1;
- zepsute[v] = d;
- } else {
- VI w;
- FORE(j, g[v]) {
- w.pb(val[*j]);
- zepsute[v] = min(zepsute[v], zepsute[*j]+1);
- }
- if (zepsute[v] == d) val[v] = 1;
- else val[v] = 0;
- sort(all(w));
- int maxi = w.back();
- if (maxi + zepsute[v] < d) val[v] = 0;
- else if (maxi + maxi < d) val[v] = maxi+1;
- else {
- val[v] = 0;
- FOR(j,0,w.size()) if (w[j] == maxi) ans++;
- FOR(j,0,w.size()) if (w[j] != maxi && w[j]+maxi >= d) val[v] = w[j] + 1;
- zepsute[v] = min(zepsute[v], maxi);
- }
- }
- //debug(ans);
- //debug3(v, val[v], zepsute[v]);
- }
- if ((zepsute[0] >= d) || (val[0] + val[0] >= d && val[0] + zepsute[0] >= d)) ans++;
- printf("%d\n", ans);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement