Advertisement
Guest User

Untitled

a guest
Dec 15th, 2019
97
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.92 KB | None | 0 0
  1. #include <vector>
  2. #include <iostream>
  3. #include <algorithm>
  4.  
  5. struct Tree {
  6.     Tree(int N) {
  7.         edges.resize(N);
  8.         depth.resize(N);
  9.         visited.resize(N);
  10.         answers.resize(N, -1);
  11.     }
  12.     void AddEdge(int u, int v);
  13.     void DfsForDepth(int vertex, int dep);
  14.     int FindMaxDepth();
  15.     void FindDiameter();
  16.     int DfsForDiameter(int vertex, int dep);
  17.     void DfsForOthers(int vertex, int answer);
  18.     void GetAnswer();
  19.     std::vector<int> answers;
  20. private:
  21.     std::vector<std::vector<int> > edges;
  22.     std::vector<int> depth;
  23.     std::vector<bool> visited;
  24.     int DiameterBegin;
  25.     int DiameterEnd;
  26. };
  27.  
  28. void Tree::AddEdge(int u, int v) {
  29.     edges[u].push_back(v);
  30.     edges[v].push_back(u);
  31. }
  32.  
  33. void Tree::DfsForDepth(int vertex, int dep) {
  34.     visited[vertex] = true;
  35.     depth[vertex] = dep;
  36.     for (int i = 0; i < edges[vertex].size(); i++) {
  37.         int u = edges[vertex][i];
  38.         if (visited[u] == false) {
  39.             DfsForDepth(u, dep + 1);
  40.         }
  41.     }
  42. }
  43.  
  44. int Tree::FindMaxDepth() {
  45.     int maxDepth = -1;
  46.     int numMax;
  47.     for (int i = 0; i < depth.size(); i++) {
  48.         if (depth[i] > maxDepth) {
  49.             maxDepth = depth[i];
  50.             numMax = i;
  51.         }
  52.     }
  53.     return numMax;
  54. }
  55.  
  56. void Tree::FindDiameter() {
  57.     visited.assign(visited.size(), false);
  58.     DfsForDepth(0, 0);
  59.     DiameterBegin = FindMaxDepth();
  60.  
  61.     visited.assign(visited.size(), false);
  62.     DfsForDepth(DiameterBegin, 0);
  63.     DiameterEnd = FindMaxDepth();
  64. }
  65.  
  66. int Tree::DfsForDiameter(int vertex, int dep) {
  67.     visited[vertex] = true;
  68.  
  69.     if (vertex == DiameterEnd) {
  70.         answers[vertex] = dep;
  71.         return 0;
  72.     }
  73.  
  74.     int result = -1;
  75.  
  76.     for (int i = 0; i < edges[vertex].size(); i++) {
  77.         int u = edges[vertex][i];
  78.         if (!visited[u]) {
  79.             result = DfsForDiameter(u, dep + 1);
  80.             if (result != -1) {
  81.                 answers[vertex] = std::max(result + 1, dep);
  82.                 break;
  83.             }
  84.         }
  85.     }
  86.  
  87.     return result + 1;
  88. }
  89.  
  90. void Tree::DfsForOthers(int vertex, int answer) {
  91.     visited[vertex] = true;
  92.  
  93.     if (answers[vertex] == -1) {
  94.         answers[vertex] = answer;
  95.     }
  96.  
  97.     for (int i = 0; i < edges[vertex].size(); i++) {
  98.         int u = edges[vertex][i];
  99.         if (!visited[u]) {
  100.             DfsForOthers(u, answers[vertex] + 1);
  101.         }
  102.     }
  103. }
  104.  
  105. void Tree::GetAnswer() {
  106.     FindDiameter();
  107.     visited.assign(visited.size(), false);
  108.     DfsForDiameter(DiameterBegin, 0);
  109.     visited.assign(visited.size(), false);
  110.     DfsForOthers(DiameterBegin, -1);
  111. }
  112.  
  113. int main() {
  114.     int N;
  115.     std::cin >> N;
  116.     Tree tree(N);
  117.  
  118.     for (int i = 0; i < N - 1; i++) {
  119.         int u, v;
  120.         std::cin >> u >> v;
  121.         tree.AddEdge(u, v);
  122.     }
  123.  
  124.     tree.GetAnswer();
  125.     for (int i = 0; i < tree.answers.size(); i++) {
  126.         std::cout << tree.answers[i] << "\n";
  127.     }
  128. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement