fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. const int MAXN = 200000;
  8. vector<int> graph[MAXN + 1];
  9. int maxDist[MAXN + 1];
  10. int subtreeSize[MAXN + 1];
  11.  
  12. void dfs(int node, int parent, int depth) {
  13.     maxDist[node] = depth;
  14.     for (int neighbor : graph[node]) {
  15.         if (neighbor != parent) {
  16.             dfs(neighbor, node, depth + 1);
  17.         }
  18.     }
  19. }
  20.  
  21. void reroot(int node, int parent, int n) {
  22.     // Store the maximum distance for the current node
  23.     vector<int> distances;
  24.     for (int neighbor : graph[node]) {
  25.         if (neighbor != parent) {
  26.             distances.push_back(maxDist[neighbor]);
  27.         }
  28.     }
  29.  
  30.     // Sort distances to find the two largest
  31.     sort(distances.rbegin(), distances.rend());
  32.  
  33.     for (int neighbor : graph[node]) {
  34.         if (neighbor != parent) {
  35.             // Calculate the maximum distance for the current neighbor
  36.             int originalMax = maxDist[node];
  37.             int newMax = (distances.size() > 0 ? distances[0] : 0);
  38.             if (distances[0] == maxDist[neighbor]) {
  39.                 newMax = (distances.size() > 1 ? distances[1] : 0);
  40.             }
  41.             maxDist[neighbor] = max(maxDist[neighbor], originalMax + 1);
  42.             reroot(neighbor, node, n);
  43.             maxDist[neighbor] = originalMax; // Restore original maxDist
  44.         }
  45.     }
  46. }
  47.  
  48. int main() {
  49.     int n;
  50.     cin >> n;
  51.  
  52.     for (int i = 0; i < n - 1; ++i) {
  53.         int a, b;
  54.         cin >> a >> b;
  55.         graph[a].push_back(b);
  56.         graph[b].push_back(a);
  57.     }
  58.  
  59.     // First DFS to find the farthest node from node 1
  60.     dfs(1, -1, 0);
  61.  
  62.     // Find the farthest node from node 1
  63.     int farthestNode = 1;
  64.     for (int i = 1; i <= n; ++i) {
  65.         if (maxDist[i] > maxDist[farthestNode]) {
  66.             farthestNode = i;
  67.         }
  68.     }
  69.  
  70.     // Second DFS from the farthest node found
  71.     fill(maxDist, maxDist + n + 1, 0);
  72.     dfs(farthestNode, -1, 0);
  73.  
  74.     // Rerooting to calculate maximum distances for all nodes
  75.     reroot(farthestNode, -1, n);
  76.  
  77.     // Output the maximum distances
  78.     for (int i = 1; i <= n; ++i) {
  79.         cout << maxDist[i] << " ";
  80.     }
  81.     cout << endl;
  82.  
  83.     return 0;
  84. }
Success #stdin #stdout 0.01s 8188KB
comments (?)
stdin
copy 
5
1 2
1 3
3 4
3 5
stdout
copy 
1 2 0 0 1
https://ideone.com/02DIsM
language:
C++ (gcc 8.3)
created:
9 days 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!