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;
  10. 	cin >> n;
  11.  
  12. 	vector<vector<int>> g(n + 1, vector<int>());
  13.  
  14. 	for(int i = 2; i <= n; i++){
  15. 		int x;
  16. 		cin >> x;
  17. 		g[x].push_back(i);
  18. 	}
  19.  
  20. 	int ans = n;
  21. 	vector<int> dp(n + 1, 0);
  22. 	auto dfs = [&](int x, auto && self) -> void {
  23. 		for(auto y: g[x]){
  24. 			self(y, self);
  25. 		}
  26.  
  27. 		multiset<int> p;
  28.  
  29. 		for(auto y: g[x]){
  30. 			p.insert(dp[y]);
  31. 		}
  32. 		if(!p.size())return;
  33.  
  34. 		while(p.size() > 2){
  35. 			auto x = *(p.begin());
  36. 			p.erase(p.find(x));
  37. 			auto y = *(p.begin());
  38. 			p.erase(p.find(y));
  39. 			p.insert(max(x, y) + 1);
  40. 		}
  41. 		int h = *(p.begin());
  42. 		p.erase(p.find(h));
  43. 		if(p.size()){
  44. 			int g = *(p.begin());
  45. 			dp[x] = max(g, h) + 1;
  46. 		}
  47. 		else dp[x] = h + 1;
  48. 	};
  49. 	dfs(1, dfs);
  50.  
  51. 	cout << dp[1] << "\n";
  52. }
  53.  
  54. int main(){
  55. 	ios_base::sync_with_stdio(false);
  56. 	cin.tie(nullptr);
  57.  
  58. 	int t = 1;
  59. 	cin >> t;
  60.  
  61. 	for(int i = 1; i <= t; i++){
  62. 		solve();
  63. 	}
  64. 	return 0;
  65. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
 5
6
1 2 2 1 1
15
1 1 2 2 3 3 4 4 5 5 6 6 7 7
5
1 2 2 2
7
1 1 2 1 1 2
10
1 1 1 2 2 2 4 3 3
stdout
copy 
2
3
3
3
3
https://ideone.com/nSVdPH
language:
C++14 (gcc 8.3)
created:
5 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!