Advertisement
Guest User

Untitled

a guest
Oct 23rd, 2019
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.93 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define sz(v) (int)v.size()
  6. #define all(v) v.begin(), v.end()
  7. #define pb emplace_back
  8. #define mp make_pair
  9. #define debug(x) cout << #x << " = " << x << endl;
  10. #define F first
  11. #define S second
  12.  
  13. const int N = 2e5;
  14.  
  15. vector<int> g[N + 1];
  16. int n;
  17.  
  18. pair<pair<int, int>, pair<int, int>> dp[N + 1];
  19. int max_path[N + 1][2], parent[N + 1];
  20.  
  21. // dp[i].first - (max1_len, max1_ver)
  22. // dp[i].second - (max2_len, max2_ver)
  23.  
  24. void dfs(int cur, int prev) {
  25.     parent[cur] = prev;
  26.     vector<pair<int, int>> p = {{0, 0}, {0, 0}};
  27.     for (auto v : g[cur]) {
  28.         if (v == prev) continue;
  29.  
  30.         dfs(v, cur);
  31.         p.pb(mp(1 + dp[v].F.F, v));
  32.     }
  33.     auto iter = max_element(all(p));
  34.     dp[cur].F = {*iter};
  35.     p.erase(iter);
  36.     iter = max_element(all(p));
  37.     dp[cur].S = {*iter};
  38. }
  39.  
  40. void calc(int v) {
  41.     if (max(max_path[v][0], max_path[v][1]) != 0) return;
  42.     if (v == 1) {
  43.         max_path[v][0] = dp[v].F.F;
  44.         return;
  45.     }
  46.     if (max(max_path[parent[v]][1], max_path[parent[v]][0]) == 0) {
  47.         calc(parent[v]);
  48.     }
  49.     max_path[v][0] = dp[v].F.F;
  50.     max_path[v][1] = max_path[parent[v]][1] + 1;
  51.     if (dp[parent[v]].F.S == v) {
  52.         max_path[v][1] = max(max_path[v][1], 1 + dp[parent[v]].S.F);
  53.     } else {
  54.         max_path[v][1] = max(max_path[v][1], 1 + dp[parent[v]].F.F);
  55.     }
  56. }
  57.  
  58. signed main() // check the limits, dummy
  59. {
  60.     ios::sync_with_stdio(false);
  61.     cin >> n;
  62.     for (int i = 0; i < n - 1; i++) {
  63.         int u, v;
  64.         cin >> u >> v;
  65.         g[u].pb(v);
  66.         g[v].pb(u);
  67.     }
  68.  
  69.     /*
  70.     firstly we gonna find max1_len and max2_len path
  71.     for each node, where path includes only children nodes
  72.     */
  73.     dfs(1, -1);
  74.  
  75.     for (int i = 2; i <= n; i++) {
  76.         calc(i);
  77.     }
  78.     for (int i = 1; i <= n; i++) {
  79.         cout << max(max_path[i][0], max_path[i][1]) << endl;
  80.     }
  81. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement