fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll long long
  6. #define pb push_back
  7. #define mp make_pair
  8. #define F first
  9. #define S second
  10. #define make0(a) memset(a,0,sizeof(a))
  11. #define make1(a) memset(a,-1,sizeof(a))
  12. #define all(v) v.begin(),v.end()
  13. #define sc(i) scanf("%d",&i)
  14. #define pi pair <int,int>
  15.  
  16. const int mod = 1e9+7;
  17. const int N = 1e5+1;
  18.  
  19. int max(int a,int b,int c) { return max(max(a,b),c); }
  20. int max(int a[],int n) { int mx=a[0]; for(int i=0;i<n;i++) {if(mx<a[i]) { mx=a[i]; } } return mx;}
  21. int max(vector<int> a) { int n=a.size(); int mx=a[0]; for(int i=0;i<n;i++) {if(mx<a[i]) { mx=a[i]; } } return mx;}
  22.  
  23. int min(int a,int b,int c) { return min(min(a,b),c); }
  24. int min(int a[],int n) { int mn=a[0]; for(int i=0;i<n;i++) {if(mn>a[i]) { mn=a[i]; } } return mn;}
  25. int min(vector<int> a) { int n=a.size(); int mn=a[0]; for(int i=0;i<n;i++) {if(mn>a[i]) { mn=a[i]; } } return mn;}
  26.  
  27. void input(int a[],int n) { for (int i = 0; i < n; ++i) { scanf("%d",&a[i]); } }
  28. void input(vector <int> &a,int n) { for (int i = 0; i < n; ++i) { scanf("%d",&a[i]); } }
  29.  
  30. bool isPalin(string str) { int n=str.size(); for(int i=0;i<n/2;i++) { if(str[i] != str[n-1-i]) return false;} return true; }
  31.  
  32. vector <int> adjlist[N];
  33.  
  34. int f[N],g[N];
  35. int dia = 0;
  36.  
  37. void dfs(int i)
  38. {
  39. 	vector <int> fv;
  40. 	for(int j : adjlist[i])
  41. 	{
  42. 		dfs(j);
  43. 		fv.pb(f[j]);
  44. 	}
  45. 	sort(all(fv));
  46. 	f[i] = 0;
  47. 	if(fv.size() > 0)
  48. 	{
  49. 		f[i] = 1 + fv.back();
  50. 	}
  51. 	if(fv.size() >= 2)
  52. 	{
  53. 		g[i] = 2 + fv.back() + fv[fv.size()-2];
  54. 	}
  55. 	// for(int x : fv)
  56. 	// 	cout << x << ' ';
  57. 	// cout << endl;
  58. 	dia = max(dia,g[i],f[i]);
  59. }
  60.  
  61. int main()
  62. {
  63. 	int n;
  64. 	cin >> n; // number of nodes
  65. 	for(int i=2;i<=n;i++)
  66. 	{
  67. 		int a;
  68. 		cin >> a; // parent of the ith node.
  69. 		adjlist[a].pb(i);
  70. 	}
  71. 	dfs(1);
  72. 	cout << dia << endl;
  73. 	return 0;
  74. }
Success #stdin #stdout 0s 5428KB
comments (?)
stdin
copy 
4
1 1 1
stdout
copy 
2
https://ideone.com/RazeS4
language:
C++14 (gcc 8.3)
created:
8 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!