fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long 
  4. #define maxn 100010
  5. ll dead[maxn], sz[maxn];
  6. vector <ll> g[maxn];
  7. vector <ll> cen_tree[maxn];
  8. void get_sz(ll src, ll par)
  9. {
  10. 	sz[src]=1;
  11. 	for(auto x: g[src])
  12. 	{
  13. 		if(x==par || dead[x]==1) continue;
  14. 		get_sz(x, src);
  15. 		sz[src]+=sz[x];
  16. 	}
  17. }
  18.  
  19.  
  20. ll find_centroid(ll src)
  21. {
  22. 	while(1)
  23. 	{
  24. 	ll mx=0, v=-1;
  25. 	for(auto x: g[src])
  26. 	{
  27. 		if(dead[x]==1) continue;
  28. 		if(sz[x]>mx) mx=sz[x], v=x;
  29. 	}
  30. 	if(mx<=sz[src]/2) return src;
  31. 	sz[src]-=mx;
  32. 	sz[v]+=sz[src];
  33. 	src=v;
  34. 	}
  35. 	return src;
  36. }
  37.  
  38.  
  39. void form_tree(ll src)
  40. {
  41. 	get_sz(src, -1LL);
  42. 	src=find_centroid(src);
  43. 	dead[src]=1;
  44. 	queue <ll> q;
  45. 	q.push(src);
  46.  
  47. 	while(q.size())
  48. 	{
  49. 		ll x=q.front();
  50. 		q.pop();
  51. 		for(auto h: g[x])
  52. 		{
  53. 			if(dead[h]==1) continue;
  54. 			ll c=find_centroid(h);
  55. 			dead[c]=1;
  56. 			cen_tree[x].push_back(c);
  57. 			q.push(c);
  58. 		}
  59. 	}
  60.  
  61. }
  62.  
  63.  
  64.  
  65. int main()
  66. {
  67. 	ll x, i, j, m, n, u, v;
  68.  
  69. 	scanf("%lld", &n);
  70.  
  71. 	for(i=0; i<n-1; i++)
  72. 	{
  73. 		scanf("%lld %lld", &u, &v);
  74. 		g[u].push_back(v);
  75. 		g[v].push_back(u);
  76. 	}
  77.  
  78.  
  79. 	form_tree(1LL);
  80.  
  81. 	for(i=1; i<=n; i++)
  82. 	{
  83. 		printf("%lld: ", i);
  84. 		for(auto x: cen_tree[i]) printf("%lld ", x);
  85. 		printf("\n");
  86. 	}
  87.  
  88.  
  89.  
  90. 	return 0;
  91. }
Runtime error #stdin #stdout 0s 7980KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/EuKp1v
language:
C++14 (gcc 8.3)
created:
4 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!