Guest User

Untitled

a guest
Oct 19th, 2017
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.88 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. class Node
  9. {
  10. public:
  11. Node() : h(0) {}
  12.  
  13. int h;
  14. vector<int> child;
  15. };
  16.  
  17. int root;
  18. int max_path;
  19. vector<Node> nodes;
  20.  
  21. bool mycmp(int a, int b)
  22. {
  23. return (nodes[b].h < nodes[a].h);
  24. }
  25.  
  26. int DFS(int idx)
  27. {
  28. if (nodes[idx].child.empty()) {
  29. nodes[idx].h = 1;
  30. return 1;
  31. }
  32.  
  33. for (int i=0;i<nodes[idx].child.size();i++) {
  34. nodes[idx].h = max(nodes[idx].h, DFS(nodes[idx].child[i]) + 1);
  35. }
  36. sort(nodes[idx].child.begin(), nodes[idx].child.end(), mycmp);
  37. if (nodes[idx].child.size() == 1) {
  38. max_path = max(max_path, nodes[nodes[idx].child[0]].h);
  39. }
  40. else {
  41. max_path = max(max_path, nodes[nodes[idx].child[0]].h + nodes[nodes[idx].child[1]].h);
  42. }
  43. return nodes[idx].h;
  44. }
  45.  
  46. void calc(int idx)
  47. {
  48. for (int i=0;i<nodes[idx].child.size();i++) {
  49. nodes[idx].h = max(nodes[idx].h, DFS(nodes[idx].child[i]) + 1);
  50. }
  51. sort(nodes[idx].child.begin(), nodes[idx].child.end(), mycmp);
  52. if (nodes[idx].child.size() == 1) {
  53. max_path = max(max_path, nodes[nodes[idx].child[0]].h);
  54. }
  55. else {
  56. max_path = max(max_path, nodes[nodes[idx].child[0]].h + nodes[nodes[idx].child[1]].h);
  57. }
  58. }
  59.  
  60. int main()
  61. {
  62. int n;
  63. int parent, child;
  64. while (cin >> n) {
  65. vector<int> pp(n, -1);
  66. root = -1;
  67. max_path = 0;
  68. nodes.clear();
  69. for (int i=0;i<n;i++) {
  70. Node node;
  71. nodes.push_back(node);
  72. }
  73. for (int i=0;i<n-1;i++) {
  74. cin >> parent >> child;
  75. pp[child] = parent;
  76. nodes[parent].child.push_back(child);
  77. }
  78. for (int i=0;i<n;i++) {
  79. if (pp[i] == -1) {
  80. root = i;
  81. break;
  82. }
  83. }
  84. calc(root);
  85. cout << max_path << endl;
  86. }
  87. return 0;
  88. }
Add Comment
Please, Sign In to add comment