Advertisement
Guest User

temp

a guest
Mar 14th, 2020
500
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.12 KB | None | 0 0
  1. * Think twice, code once.
  2. * 1.integer overflow(maybe even long long overflow : (a+b >= c) -> (a >= c-b)
  3. * 2.runtime error
  4. * 3.boundary condition
  5. * ---------------------------------------------------------------------------------------
  6. * Author : zzy
  7. * Date : 2020-03-14-18.59.59 Saturday
  8. */
  9. #include <bits/stdc++.h>
  10.  
  11. #define eb emplace_back
  12. #define mp make_pair
  13. #define mt make_tuple
  14. #define fi first
  15. #define se second
  16. #define pb push_back
  17. #define all(x) (x).begin(), (x).end()
  18. #define rall(x) (x).rbegin(), (x).rend()
  19. #define forn(i, n) for (int i = 0; i < (int)(n); ++i)
  20. #define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
  21. #define ford(i, a, b) for (int i = (int)(a); i >= (int)b; --i)
  22. #define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
  23. #define rep(i, l, r) for (int i = (l); i <= (r); i++)
  24. #define per(i, r, l) for (int i = (r); i >= (l); i--)
  25. #define ms(x, y) memset(x, y, sizeof(x))
  26. #define SZ(x) ((int)(x).size())
  27.  
  28. using namespace std;
  29.  
  30. typedef pair<int, int> pii;
  31. typedef vector<int> vi;
  32. typedef vector<pii> vpi;
  33. typedef vector<vi> vvi;
  34. typedef long long i64;
  35. typedef vector<i64> vi64;
  36. typedef vector<vi64> vvi64;
  37. typedef pair<i64, i64> pi64;
  38. typedef double ld;
  39.  
  40. template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
  41. template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }
  42.  
  43. const int maxn = 5*(int)1e5+100;
  44. int n, ans[maxn], no1[maxn], no2[maxn];
  45. vvi g(maxn);
  46.  
  47. void dfs1(int u, int par) {
  48.     for (int to : g[u]) {
  49.         if(to == par) continue;
  50.         dfs1(to, u);
  51.         if (no1[to]+1 > no1[u]) {
  52.             swap(no1[u], no2[u]);
  53.             no1[u] = no1[to]+1;
  54.         } else if (no1[to]+1 > no2[u]) {
  55.             no2[u] = no1[to]+1;
  56.         }
  57.     }
  58. }
  59. void dfs2(int u, int par, int dist = 0) {
  60.     ans[u] = max(no1[u], dist);
  61.     for (int to : g[u]) {
  62.         if (to == par) continue;
  63.         if (no1[to]+1 == no1[u]) {
  64.             if (no2[u]+1 > no1[to]) {
  65.                 swap(no1[to], no2[to]);
  66.                 no1[to] = no2[u]+1;
  67.             }
  68.             if (no2[u]+1 > no2[to]) {
  69.                 no2[to] = no2[u]+1;
  70.             }
  71.             dfs2(to, u, no2[u]+1);
  72.         } else {
  73.             if (no1[u]+1 > no1[to]) {
  74.                 swap(no1[to], no2[to]);
  75.                 no1[to] = no1[u]+1;
  76.             }
  77.             if (no1[u]+1 > no2[to]) {
  78.                 no2[to] = no1[u]+1;
  79.             }
  80.             dfs2(to, u, no1[u]+1);
  81.         }
  82.     }
  83. }
  84.  
  85. int main() {
  86.     ios::sync_with_stdio(false);
  87.     cin.tie(nullptr);
  88.     cout.precision(10);
  89.     cout << fixed;
  90. #ifdef LOCAL_DEFINE
  91.     freopen("input.txt", "r", stdin);
  92. #endif
  93.  
  94.     ms(no1, 0);
  95.     ms(no2, 0);
  96.     cin >> n;
  97.     forn(i, n-1) {
  98.         int u, v;
  99.         cin >> u >> v;
  100.         g[u].eb(v);
  101.         g[v].eb(u);
  102.     }
  103.     dfs1(1, 0);
  104. //    for1(i, n) {
  105. //        cout << i << ' ' << no1[i] << ' ' << no2[i] << endl;
  106. //    }
  107.     dfs2(1, 0);
  108.  //   cerr << "YES" << endl;
  109.     for1(i, n) cout << ans[i]+1 << '\n';
  110.  
  111. #ifdef LOCAL_DEFINE
  112.     cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  113. #endif
  114.     return 0;
  115. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement