fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define all(v) begin(v), end(v)
  3. using namespace std;
  4.  
  5. const int MX = 1e5;
  6. struct Tree{
  7. 	vector<int> adj[MX];
  8. 	int depth[MX];
  9. 	int parent[MX];
  10. 	vector<int> layers[MX];
  11. 	int maxDepth;
  12.  
  13. 	void addEdge(int u, int v) {
  14. 		adj[u].push_back(v);
  15. 		adj[v].push_back(u);
  16. 	}
  17.  
  18. 	void dfs(int u, int p = -1) {
  19. 		maxDepth = max(maxDepth, depth[u]);
  20. 		parent[u] = p;
  21. 		layers[depth[u]].push_back(u);
  22. 		for (int v : adj[u]) {
  23. 			if (v == p) continue;
  24. 			depth[v] = depth[u] + 1;
  25. 			dfs(v, u);
  26. 		}
  27. 	}
  28.  
  29. 	vector<int> encode(int root, int n) { //O(n log n)
  30. 		//The code will have size exactly 2n - 1
  31. 		maxDepth = 0;
  32. 		depth[root] = 0;
  33. 		dfs(root);
  34.  
  35. 		vector<int> label(n);
  36. 		vector<int> code;
  37. 		vector<vector<int>> childrenCode(n);
  38. 		auto cmpNode = [&](int &u, int &v) {
  39. 			return childrenCode[u] < childrenCode[v];
  40. 		};
  41. 		for (int d = maxDepth; d >= 0; d--) {
  42. 			sort(layers[d].begin(), layers[d].end(), cmpNode);
  43. 			for (int i = 0; i < layers[d].size(); i++) {
  44. 				//***************Label Assignment**********************
  45. 				int u = layers[d][i];
  46. 				if (i == 0) label[u] = 1;
  47. 				else {
  48. 					int prev = layers[d][i - 1];
  49. 					label[u] = label[prev];
  50. 					if (childrenCode[u] != childrenCode[prev]) {
  51. 						label[u]++;
  52. 					}
  53. 				}
  54. 				//Keep building childrenCode of the parent of u
  55. 				if (d != 0) childrenCode[parent[u]].push_back(label[u]);
  56. 				//***************Code generation**********************
  57. 				code.push_back(0); //group separator
  58. 				copy(all(childrenCode[u]), back_inserter(code));
  59. 			}
  60. 			layers[d].clear();
  61. 		}
  62. 		return code;
  63. 	}
  64. } tree;
  65.  
  66. int main() {
  67. 	ios_base::sync_with_stdio(false);
  68. 	cin.tie(0);
  69.  
  70. 	//USAGE
  71. 	int n;
  72. 	cin >> n;
  73. 	for (int i = 0; i < n - 1; i++) {
  74. 		int u, v;
  75. 		cin >> u >> v;
  76. 		u--;
  77. 		v--;
  78. 		tree.addEdge(u, v);
  79. 	}
  80. 	int root = 0;
  81. 	auto code = tree.encode(root, n);
  82. 	for (int x : code) cout << x << " ";
  83. 	cout << "\n";
  84. 	return 0;
  85. }
  86.  
Success #stdin #stdout 0.01s 9004KB
comments (?)
stdin
copy 
8
1 2
1 3
3 4
3 5
3 6
2 7
2 8
stdout
copy 
0 0 0 0 0 0 1 1 0 1 1 1 0 1 2
https://ideone.com/lUOoVL
language:
C++14 (gcc 8.3)
created:
2 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!