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. 	vector<vector<int>> g(n, vector<int>());
  12.  
  13. 	for(int i = 1; i < n; i++){
  14. 		int x;
  15. 		cin >> x;
  16. 		x--;
  17. 		g[x].push_back(i);
  18. 		g[i].push_back(x);
  19. 	}
  20.  
  21. 	int s = 1, e = n - 1;
  22. 	int mid;
  23. 	int cnt = 0;
  24. 	multiset<tuple<int, int, int>> ms;
  25. 	auto dfs = [&](int x, int par, int c, bool toDo, auto && self) -> int {
  26. 		int h = 1;
  27. 		for(auto y: g[x]){
  28. 			if(y != par){
  29. 				h = max(h, self(y, x, c + 1, ((c % mid) == 0), self) + 1);
  30. 			}
  31. 		}
  32. 		if(toDo)cnt++;
  33. 		ms.insert({h, c, toDo});
  34. 		return h;
  35. 	};
  36. 	int ans = n - 1;
  37. 	while(s <= e){
  38. 		mid = s + (e - s) / 2;
  39.  
  40. 		int tot = 0;
  41. 		for(auto y: g[0]){
  42. 			cnt = 0;
  43. 			ms.clear();
  44. 			int h = dfs(y, 0, 1, false, dfs);
  45. 			int mi = h;
  46. 			for(int i = 0; i < h; i++){
  47. 				while(ms.size()){
  48. 					auto [p, q, r] = *(ms.begin());
  49. 					if(p > i)break;
  50. 					ms.erase(ms.find({p, q, r}));
  51. 					if(r)cnt--;
  52. 				}
  53. 				mi = min(mi, i + cnt);
  54. 			}
  55. 			tot += mi;
  56. 		}
  57. 		if(mid == 1){
  58. 			cout << tot << "\n";
  59. 		}
  60.  
  61. 		if(tot <= k){
  62. 			ans = mid;
  63. 			e = mid - 1;
  64. 		}else{
  65. 			s = mid + 1;
  66. 		}
  67.  
  68. 	}
  69. 	cout << ans << "\n";
  70.  
  71. }
  72.  
  73. int main(){
  74. 	ios_base::sync_with_stdio(false);
  75. 	cin.tie(nullptr);
  76.  
  77. 	int t = 1;
  78. 	cin >> t;
  79.  
  80. 	for(int i = 1; i <= t; i++){
  81. 		solve();
  82. 	}
  83. 	return 0;
  84. }
  85.  
Success #stdin #stdout 0.01s 5292KB
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
1
1
5
4
3
0
1
https://ideone.com/7HcPnU
language:
C++14 (gcc 8.3)
created:
1 day 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!