fork download
copy 
  1. // first second push_back unordered return continue break vector visited check flag bool while iterator begin end lower_bound upper_bound temp true false ll_MAX ll_MIN insert erase clear pop push compare ll64_MAX ll64_MIN  reverse replace stringstream string::npos length substr front priority_queue
  2.  
  3. #ifndef ONLINE_JUDGE
  4. #include "debug.h"
  5. #else
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8. #define debug(...) 42
  9. #endif
  10.  
  11. #define ll long long
  12. #define rep(i,x,n,inc) for(i=x ; i<n ; i+=inc)
  13.  
  14. const ll sz = 300119;
  15. std::vector<ll> adj[sz];
  16.  
  17. ll dep[sz], di;
  18. vector<ll>d1(sz, 0), el, vis(sz, 0), d2(sz, 0), d3(sz, 0);
  19.  
  20. ll dfs(ll u , ll h) {
  21. 	vis[u] = 1;
  22. 	d1[u] = h;
  23. 	ll f = 0, s = 0;
  24. 	for (auto v : adj[u]) {
  25. 		if (!vis[v]) {
  26. 			ll sub = dfs(v, h + 1);
  27.  
  28. 			f = max(sub, f);
  29. 			if (f > s)	swap(f, s);
  30. 		}
  31. 	}
  32. 	d2[u] = f, d3[u] = s;
  33. 	di = max({di, d2[u] + d3[u]});
  34.  
  35. 	return max(1LL + d2[u], 1LL + d3[u]);
  36. }
  37.  
  38. void bfs(ll u , ll h = 0) {
  39. 	vis[u] = 1;
  40. 	debug(u, h);
  41. 	if ((adj[u].size() == 1) and h)	el.push_back(u);
  42.  
  43. 	for (auto v : adj[u]) {
  44. 		if (!vis[v]) {
  45. 			ll z = max(d2[v], d3[v]) + 1;
  46.  
  47. 			if (z == di) {
  48. 				el.push_back(u);
  49. 				bfs(v, 1);
  50. 			} else if (d2[u] + d3[u] == di and (z == d2[u] or z == d3[u])) {
  51. 				// } else if ((z == d2[u] or z == d3[u])) {
  52. 				// debug(v);
  53. 				bfs(v, 1);
  54. 			}
  55. 			else {
  56. 				bfs(v, h);
  57. 			}
  58. 		}
  59. 	}
  60.  
  61. 	if (max(d2[u], d3[u]) == di) {
  62. 		// debug(u);
  63. 		el.push_back(u);
  64. 	}
  65. }
  66.  
  67. int32_t main() {
  68. 	ios::sync_with_stdio(0); 		cin.tie(0); cout.tie(0);
  69.  
  70. 	ll t, i, x, j, y, 	z, k, n;
  71. 	cin >> n;
  72.  
  73. 	rep(i, 0, n - 1, 1) {
  74. 		cin >> x >> y;
  75. 		adj[x].push_back(y);
  76. 		adj[y].push_back(x);
  77. 	}
  78.  
  79. 	dfs(1, 0);
  80. 	vector<ll>ans(n + 1);
  81.  
  82. 	rep(i, 0, 1 + n, 1)	{
  83. 		ans[i] = di;
  84. 		vis[i] = 0;
  85. 	}
  86. 	bfs(1, 0);
  87.  
  88. 	for (auto zx : el)	ans[zx] = di + 1;
  89.  
  90. 	rep(i, 1, 1 + n, 1)	cout << ans[i] << " ";
  91. 	debug(di, ans, el);
  92. }
  93.  
  94.  
Runtime error #stdin #stdout 0s 19796KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/NF5593
language:
C++14 (gcc 8.3)
created:
3 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!