fork(1) download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/gTF8qe
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!