fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3.  
  4. using namespace std;
  5.  
  6. const int MOD = 1e9 + 7;
  7.  
  8. void solve(){
  9. 	int n, k;
  10. 	cin >> n >> k;
  11.  
  12. 	vector<vector<int>> g(n, vector<int>());
  13.  
  14. 	for(int i = 1; i < n; i++){
  15. 		int x;
  16. 		cin >> x;
  17. 		x--;
  18. 		g[i].push_back(x);
  19. 		g[x].push_back(i);
  20. 	}
  21. 	map<int, vector<int>> m;
  22. 	vector<int> d(n, 1);
  23. 	auto dfs = [&](int x, int par, int h, auto && self) -> void  {
  24. 		m[h].push_back(x);
  25.  
  26. 		for(auto y: g[x]){
  27. 			if(y != par){
  28. 				self(y, x, h + 1, self);
  29. 				d[x] = max(d[x], d[y] + 1);
  30. 			}
  31. 		}
  32. 	};
  33. 	dfs(0, -1, 0, dfs);
  34.  
  35. 	int s = 1, e = n - 1;
  36. 	int ans = n;
  37. 	while(s <= e){
  38. 		int mid = s + (e - s) / 2;
  39. 		int cnt = 0;
  40. 		for(int i = mid; i < n && cnt <= k; i += mid){
  41. 			for(auto x: m[i]){
  42. 				for(auto y: g[x]){
  43. 					if(d[y] > d[x])continue;
  44. 					if(d[y] > mid)cnt++;
  45. 				}
  46. 			}
  47. 		}
  48.  
  49. 		if(cnt > k){
  50. 			s = mid + 1;
  51. 		}else{
  52. 			e = mid - 1;
  53. 			ans = mid;
  54. 		}
  55. 	}
  56. 	cout << ans << "\n";
  57.  
  58. }
  59.  
  60. int main(){
  61. 	ios_base::sync_with_stdio(false);
  62. 	cin.tie(nullptr);
  63.  
  64. 	int t = 1;
  65. 	cin >> t;
  66.  
  67. 	for(int i = 1; i <= t; i++){
  68. 		solve();
  69. 	}
  70. 	return 0;
  71. }
Success #stdin #stdout 0s 5280KB
comments (?)
stdin
copy 
5
5 1
1 1 2 2
5 2
1 1 2 2
6 0
1 2 3 4 5
6 1
1 2 3 4 5
4 3
1 1 1
stdout
copy 
1
1
3
2
1
https://ideone.com/B6adV0
language:
C++14 (gcc 8.3)
created:
2 days 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!