fork(1) download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. vector<int>edge[100005];
  6. int dp[100005],x;
  7.  
  8. int rec(int v)
  9. {
  10. if(dp[v]>=0) return dp[v];
  11. vector<int>vec;
  12. for(int i=0;i<edge[v].size();i++)
  13. {
  14. vec.push_back(rec(edge[v][i]));
  15. }
  16. sort(vec.begin(),vec.end(),greater<int>());
  17. int sum=0;
  18. for(int i=0;i<vec.size();i++)
  19. {
  20. if(i == x) break;
  21. sum+=vec[i];
  22. }
  23. return dp[v] = sum+1;
  24. }
  25. int main()
  26. {
  27. int n,m;
  28. scanf("%d %d",&n,&m);
  29. for(int i=2;i<=n;i++)
  30. {
  31. int x; scanf("%d",&x);
  32. edge[x].push_back(i);
  33. }
  34. int lb=-1,ub=n;
  35. while(ub-lb > 1)
  36. {
  37. int mid=(lb+ub)>>1;
  38. x=mid;
  39. memset(dp,-1,sizeof(dp));
  40. rec(1);
  41. if(dp[1] >= m) ub=mid;
  42. else lb=mid;
  43. }
  44. printf("%d\n",ub);
  45. }
Success #stdin #stdout 0s 4908KB
stdin
Standard input is empty
stdout
0