dnhirapara2104

https://codeforces.com/gym/102694/problem/B

Sep 24th, 2020 (edited)
213
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.73 KB | None | 0 0
  1. /*
  2. * @Author: dnhirapara
  3. * @Problem: B_Dynamic_Diameter
  4. * @Time: 28-August-2020 : ( 16:10:06 )
  5. */
  6. #include <bits/stdc++.h>
  7.  
  8. using namespace std;
  9.  
  10. /************defination************/
  11.  
  12. #define endl "\n"
  13. #define logger(x) cout << __LINE__ << ": " << #x << " -> " << (x) << endl;
  14. #define ll long long int
  15. #define ull unsigned long long int
  16.  
  17. const int size = 3e5 + 5;
  18. vector<int> g[size];
  19. vector<bool> vis(size);
  20. vector<int> deg(size);
  21. int maxDist;
  22. int maxNode;
  23. vector<int> update;
  24. vector<int> update1;
  25. bool secDfs = false;
  26.  
  27. void dfs(int node, int lvl)
  28. {
  29.     vis[node] = true;
  30.     for (auto i : g[node])
  31.     {
  32.         if (vis[i] == false)
  33.         {
  34.             dfs(i, lvl + 1);
  35.         }
  36.     }
  37.     if (secDfs && maxDist == lvl)
  38.     {
  39.         update.push_back(node);
  40.     }
  41.     if (maxDist < lvl)
  42.     {
  43.         if (secDfs)
  44.         {
  45.             update.clear();
  46.             update.push_back(node);
  47.         }
  48.         maxDist = lvl;
  49.         maxNode = node;
  50.     }
  51. }
  52. int getDia(int n)
  53. {
  54.     //first run
  55.     secDfs = false;
  56.     maxDist = -1;
  57.     for (int i = 0; i < n + 1; i++)
  58.     {
  59.         vis[i] = false;
  60.     }
  61.     dfs(1, 0);
  62.  
  63.     maxDist = -1;
  64.     int temp = maxNode;
  65.     secDfs = true;
  66.     for (int i = 0; i < n + 1; i++)
  67.     {
  68.         vis[i] = false;
  69.     }
  70.     dfs(maxNode, 0);
  71.     update.push_back(temp);
  72.     update1 = update;
  73.  
  74.     // second run
  75.     update.clear();
  76.     secDfs = false;
  77.     maxDist = -1;
  78.     for (int i = 0; i < n + 1; i++)
  79.     {
  80.         vis[i] = false;
  81.     }
  82.     dfs(maxNode, 0);
  83.  
  84.     maxDist = -1;
  85.     temp = maxNode;
  86.     secDfs = true;
  87.     for (int i = 0; i < n + 1; i++)
  88.     {
  89.         vis[i] = false;
  90.     }
  91.     dfs(maxNode, 0);
  92.     update.push_back(temp);
  93.     if (update1.size() < update.size())
  94.     {
  95.         update1 = update;
  96.     }
  97.  
  98.     //vis false
  99.     for (int i = 0; i < n + 1; i++)
  100.     {
  101.         vis[i] = false;
  102.     }
  103.     return maxDist;
  104. }
  105.  
  106. //@time comp :
  107. //@space comp :
  108. int main()
  109. {
  110.     // ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  111.     // cin.ignore(); must be there when using getline(cin, s)
  112.     ll tc = 1;
  113.     //cin >> tc;
  114.     while (tc--)
  115.     {
  116.         int n;
  117.         cin >> n;
  118.         int u, v;
  119.         for (int i = 0; i < n - 1; i++)
  120.         {
  121.             cin >> u >> v;
  122.             g[u].push_back(v);
  123.             g[v].push_back(u);
  124.         }
  125.         int degR = getDia(n);
  126.         for (auto i : update1)
  127.         {
  128.             vis[i] = true;
  129.         }
  130.         for (int i = 1; i <= n; i++)
  131.         {
  132.             if (vis[i])
  133.             {
  134.                 cout << degR + 1 << endl;
  135.             }
  136.             else
  137.             {
  138.                 cout << degR << endl;
  139.             }
  140.         }
  141.     }
  142.     return 0;
  143. }
Add Comment
Please, Sign In to add comment