Advertisement
Guest User

Untitled

a guest
Apr 28th, 2017
664
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.83 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define FOR(i,a,b) for(int i=(a);i<(b);++i)
  4. #define FORD(i, a, b) for(int i = (a); i >= (b); --i)
  5. #define VAR(v, i) __typeof(i) v=(i)
  6. #define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
  7. #define all(v) (v).begin(),(v).end()
  8.  
  9. #define PII pair<int,int>
  10. #define mp make_pair
  11. #define st first
  12. #define nd second
  13. #define pb push_back
  14. #define lint long long int
  15. #define VI vector<int>
  16.  
  17. #define debug(x) {cerr <<#x <<" = " <<x <<endl; }
  18. #define debug2(x,y) {cerr <<#x <<" = " <<x << ", "<<#y<<" = "<< y <<endl; }
  19. #define debug3(x,y,z) {cerr <<#x <<" = " <<x << ", "<<#y<<" = "<< y << ", " << #z << " = " << z <<endl; }
  20. #define debugv(x) {{cerr <<#x <<" = "; FORE(itt, (x)) cerr <<*itt <<", "; cerr <<endl; }}
  21. #define debugt(t,n) {{cerr <<#t <<" = "; FOR(it,0,(n)) cerr <<t[it] <<", "; cerr <<endl; }}
  22.  
  23. #define make( x) int (x); scanf("%d",&(x));
  24. #define make2( x, y) int (x), (y); scanf("%d%d",&(x),&(y));
  25. #define make3(x, y, z) int (x), (y), (z); scanf("%d%d%d",&(x),&(y),&(z));
  26. #define make4(x, y, z, t) int (x), (y), (z), (t); scanf("%d%d%d%d",&(x),&(y),&(z),&(t));
  27. #define makev(v,n) VI (v); FOR(i,0,(n)) { make(a); (v).pb(a);}
  28. #define IOS ios_base::sync_with_stdio(0)
  29. #define HEAP priority_queue
  30.  
  31. #define read( x) scanf("%d",&(x));
  32. #define read2( x, y) scanf("%d%d",&(x),&(y));
  33. #define read3(x, y, z) scanf("%d%d%d",&(x),&(y),&(z));
  34. #define read4(x, y, z, t) scanf("%d%d%d%d",&(x),&(y),&(z),&(t));
  35. #define readv(v,n) FOR(i,0,(n)) { make(a); (v).pb(a);}
  36. #define jeb fflush(stdout)
  37.  
  38.  
  39. using namespace std;
  40.  
  41. const int max_n = 2e5+5;
  42.  
  43. int n, d;
  44. int par[max_n];
  45. VI g[max_n];
  46. int depth[max_n];
  47. int zepsute[max_n];
  48. int val[max_n];
  49.  
  50. void dfs(int v, int h) {
  51.     depth[v] = h;
  52.     FORE(i, g[v]) {
  53.         dfs(*i, h+1);
  54.     }
  55. }
  56.  
  57.  
  58. int main() {
  59.     read2(n, d);
  60. int ans = 0;
  61.     FOR(i,0,n-1) {
  62.         make(a);
  63.         g[a].pb(i+1);
  64.         par[i+1] = a;
  65.     }
  66.     dfs(0,0);
  67.     if (d == 1) {
  68.         printf("%d\n", n);
  69.         return 0;
  70.     }
  71.     vector<PII> dupa;
  72.     FOR(i,0,n) dupa.pb(mp(depth[i], i));
  73.     sort(all(dupa));
  74.     reverse(all(dupa));
  75.     FOR(i,0,n) zepsute[i] = d;
  76.     FOR(i,0,n) {
  77.         int v = dupa[i].nd;
  78.         if (g[v].size() == 0) {
  79.             val[v] = 1;
  80.             zepsute[v] = d;
  81.         } else {
  82.             VI w;
  83.             FORE(j, g[v]) {
  84.                 w.pb(val[*j]);
  85.                 zepsute[v] = min(zepsute[v], zepsute[*j]+1);
  86.             }
  87.             if (zepsute[v] == d) val[v] = 1;
  88.             else val[v] = 0;
  89.             sort(all(w));
  90.             int maxi = w.back();
  91.             if (maxi + zepsute[v] < d) val[v] = 0;
  92.             else if (maxi + maxi < d) val[v] = maxi+1;
  93.             else {
  94.                 val[v] = 0;
  95.                 FOR(j,0,w.size()) if (w[j] == maxi) ans++;
  96.                 FOR(j,0,w.size()) if (w[j] != maxi && w[j]+maxi >= d) val[v] = w[j] + 1;
  97.                 zepsute[v] = min(zepsute[v], maxi);
  98.             }
  99.         }
  100.         //debug(ans);
  101.         //debug3(v, val[v], zepsute[v]);
  102.     }
  103.     if ((zepsute[0] >= d) || (val[0] + val[0] >= d && val[0] + zepsute[0] >= d)) ans++;
  104.    
  105.     printf("%d\n", ans);
  106. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement