fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <queue>
  5. #include <algorithm>
  6. using namespace std;
  7. vector <int> adj[100010];
  8. vector <int> adv[100010];
  9. int arr[100010],crr[100010];
  10. //vector <int> xtra;
  11. void init()
  12. {
  13. 	for(int i=0;i<100010;i++)
  14. 	{
  15. 		adj[i].clear();
  16. 		adv[i].clear();
  17. 		arr[i]=crr[i]=0;
  18. 	}
  19. 	return;
  20. }
  21.  
  22. void bfs(int idx)
  23. {
  24. 	queue <int> q;
  25. 	q.push(idx);
  26. 	while(!q.empty())
  27. 	{
  28. 		int x=q.front();
  29. 		q.pop();
  30. 		arr[adv[x][0]]=max(arr[adv[x][0]],arr[x]+1);
  31. 		if(adv[x][0]!=1)
  32. 		q.push(adv[x][0]);
  33. 		else break;
  34. 	}
  35.  
  36. 	queue <int> p;
  37. 	p.push(1);
  38. 	while(!p.empty())
  39. 	{
  40. 		int x=p.front();
  41. 		p.pop();
  42. 		int max1=0,max2=0;
  43. 		for(int i=0;i<adj[x].size();i++)
  44. 		{
  45. 			//cout<<"adj["<<x<<"]="<<adj[x][i]<<endl;;
  46. 			if(arr[adj[x][i]]>=max1)
  47. 			{
  48. 				max2=max1;
  49. 				max1=arr[adj[x][i]];
  50. 			}
  51. 		}
  52.  
  53. 		//cout<<max1<<"  "<<max2<<endl;
  54. 		crr[x]=max(max1+max2,crr[x]);
  55. 	}
  56. 	return;
  57.  
  58. }
  59.  
  60. int main()
  61. {
  62. 	int tc;
  63. 	scanf("%d",&tc);
  64. 	while(tc--)
  65. 	{
  66. 		init();
  67. 		int n;
  68. 		scanf("%d",&n);
  69. 		arr[1]=1;crr[1]=1;
  70. 		for(int i=2;i<=n;i++)
  71. 		{
  72. 			int a;
  73. 			scanf("%d",&a);
  74. 			adj[a].push_back(i);
  75. 			adv[i].push_back(a);
  76. 			arr[i]=1;crr[i]=1;
  77. 			bfs(i);
  78. 			int x,y;
  79. 			x=*(max_element(arr,arr+n));
  80. 			y=*(max_element(crr,crr+n));
  81. 			//cout<<"x="<<x-1<<"  y="<<y<<endl;
  82. 			printf("%d\n",max(x-1,y));
  83. 		}
  84. 	}
  85. 	return 0;
  86. }
Success #stdin #stdout 0s 6604KB
comments (?)
stdin
copy 
1
6
1
2
3
2
5
stdout
copy 
1
2
3
3
3
https://ideone.com/GTQnTa
language:
C++14 (gcc 8.3)
created:
11 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!