fork download 
  1. #include<bits/stdc++.h>
  2. #include<iomanip>
  3. #define fast {ios_base::sync_with_stdio(false);cin.tie(NULL);}
  4. #define ar array
  5. #define mxn 300007
  6. #define mod 1000000007
  7. #define ld long double
  8. #define pb push_back
  9. #define inf 1e18
  10. #define fi first
  11. #define se second
  12. typedef long long int ll;
  13. using namespace std;
  14. vector<ll>g[mxn];
  15. ll dis1[mxn],dis2[mxn],dis3[mxn],vis3[mxn],en,mx=-inf,en2,ans[mxn];
  16. bool vis1[mxn],vis2[mxn];
  17. int main(void){
  18. 	#ifndef ONLINE_JUDGE
  19. 	freopen("input1.txt","r",stdin);
  20. 	freopen("output.txt","w",stdout);
  21. 	#endif
  22. 	fast;
  23. 	int  n,i,a,b;
  24. 	cin>>n;
  25. 	for(i=1;i<=n-1;i++){
  26. 		cin>>a>>b;
  27. 		g[a].pb(b);
  28. 		g[b].pb(a);
  29. 	}
  30. 	queue<int>q;
  31. 	q.push(1);
  32. 	while(!q.empty()){
  33. 		int k=q.front();
  34. 		q.pop();
  35. 		vis1[k]=1;
  36. 		for(auto x:g[k]){
  37. 			if(vis1[x])
  38. 			continue;
  39. 			q.push(x);
  40. 			dis1[x]=dis1[k]+1;
  41. 			vis1[x]=1;
  42. 			if(dis1[x]>mx){
  43. 				mx=dis1[x];
  44. 				en=x;
  45. 			}
  46. 		}
  47. 	}
  48. 	q.push(en);
  49. 	mx=0;
  50. 	while(!q.empty()){
  51. 		int k=q.front();
  52. 		q.pop();
  53. 		vis2[k]=1;
  54. 		for(auto x:g[k]){
  55. 			if(vis2[x])
  56. 			continue;
  57. 			q.push(x);
  58. 			dis2[x]=dis2[k]+1;
  59. 			vis2[x]=1;
  60. 			if(dis2[x]>mx){
  61. 				mx=dis2[x];
  62. 				en2=x;
  63. 			}
  64. 		}
  65. 	}
  66. 	//cout<<en<<' '<<en2<<endl;
  67. 	for(i=1;i<=n;i++){
  68. 		if(dis2[i]==mx)
  69. 		ans[i]=mx+1;
  70. 		else
  71. 		ans[i]=max(ans[i],mx);
  72. 	}
  73. 	q.push(en2);
  74. 	while(!q.empty()){
  75. 		int k=q.front();
  76. 		q.pop();
  77. 		vis3[k]=1;
  78. 		for(auto x:g[k]){
  79. 			if(vis3[x])
  80. 			continue;
  81. 			q.push(x);
  82. 			dis3[x]=dis3[k]+1;
  83. 			vis3[x]=1;
  84. 			if(dis3[x]>mx){
  85. 				mx=dis3[x];
  86. 			}
  87. 		}
  88. 	}
  89. 	for(i=1;i<=n;i++){
  90. 		if(dis3[i]==mx)
  91. 		ans[i]=mx+1;
  92. 		else
  93. 		ans[i]=max(ans[i],mx);
  94. 	}
  95. 	for(i=1;i<=n;i++)
  96. 	cout<<ans[i]<<' ';
  97.  
  98. }
  99.  
Success #stdin #stdout 0s 10720KB
comments (?)
stdin 
5
4 2
1 4
5 4
3 4
stdout 
3 3 3 2 3
https://ideone.com/hokEIK
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!