fork download
  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
stdin
8
1 2
1 3
3 4
3 5
3 6
2 7
2 8
stdout
0 0 0 0 0 0 1 1 0 1 1 1 0 1 2