daily pastebin goal
67%
SHARE
TWEET

Untitled

a guest Feb 10th, 2016 796 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. #define forn(i, n) for (int i = 0; i < int(n); i++)
  4. #define ford(i, n) for (int i = int(n) - 1; i >= 0; i--)
  5. #define fore(i, l, r) for (int i = int(l); i < int(r); i++)
  6. #define correct(x, y, n, m) (0 <= (x) && (x) < (n) && 0 <= (y) && (y) < (m))
  7. #define all(a) (a).begin(), (a).end()
  8. #define sz(a) int((a).size())
  9. #define pb(a) push_back(a)
  10. #define mp(x, y) make_pair((x), (y))
  11. #define x first
  12. #define y second
  13.  
  14. using namespace std;
  15.  
  16. typedef long long li;
  17. typedef long double ld;
  18. typedef pair<int, int> pt;
  19.  
  20. template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
  21. template<typename X> inline X sqr(const X& a) { return a * a; }
  22.  
  23. const int INF = int(1e9);
  24. const li INF64 = li(1e18);
  25. const ld EPS = 1e-9, PI = 3.1415926535897932384626433832795;
  26.  
  27. const int N = 500500;
  28.  
  29. int n;
  30. vector<int> g[N];
  31.  
  32. inline bool read() {
  33.     if (!(cin >> n)) return false;
  34.     forn(i, n) g[i].clear();
  35.     forn(i, n - 1) {
  36.         int x, y;
  37.         assert(scanf("%d%d", &x, &y) == 2);
  38.         x--, y--;
  39.         g[x].pb(y), g[y].pb(x);
  40.     }
  41.     return true;
  42. }
  43.  
  44. vector<int> z;
  45.  
  46. void dfs(int v, int p, int d) {
  47.     int c = 0;
  48.     forn(i, sz(g[v])) {
  49.         int to = g[v][i];
  50.         if (to == p) continue;
  51.         c++;
  52.         dfs(to, v, d + 1);
  53.     }
  54.     if (!c) z.pb(d);
  55. }
  56.  
  57. int solve(int v, int p) {
  58.     z.clear();
  59.     dfs(v, p, 0);
  60.     sort(all(z));
  61.     forn(i, sz(z)) {
  62.         if (i) z[i] = max(z[i - 1] + 1, z[i]);
  63.     }
  64.     return z.back();
  65. }
  66.  
  67. inline void solve() {
  68.     int ans = 0;
  69.     forn(i, sz(g[0]))
  70.         ans = max(ans, solve(g[0][i], 0) + 1);
  71.     cout << ans << endl;
  72. }
  73.  
  74. int main() {
  75. #ifdef SU1
  76.     assert(freopen("input.txt", "rt", stdin));
  77.     //assert(freopen("output.txt", "wt", stdout));
  78. #endif
  79.    
  80.     cout << setprecision(10) << fixed;
  81.     cerr << setprecision(5) << fixed;
  82.  
  83.     while (read()) {
  84.         solve();
  85.         //break;
  86.     }
  87.    
  88.     return 0;
  89. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top