Advertisement
Guest User

Untitled

a guest
Dec 22nd, 2019
371
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.35 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <set>
  5. #include <queue>
  6. #include <algorithm>
  7. #include <string>
  8. #include <cmath>
  9. #include <cstdio>
  10. #include <iomanip>
  11. #include <fstream>
  12. #include <cassert>
  13. #include <cstring>
  14. #include <unordered_set>
  15. #include <unordered_map>
  16. #include <numeric>
  17. #include <ctime>
  18. #include <bitset>
  19. #include <complex>
  20. #include <random>
  21.  
  22. using namespace std;
  23.  
  24. vector<int> used;
  25.  
  26. vector<vector<int>> g;
  27.  
  28. void dfs(int cur, int ch, vector<int> &h) {
  29.     h[cur] = ch;
  30.     used[cur] = 1;
  31.     for (auto t : g[cur]) {
  32.         if (!used[t]) {
  33.             dfs(t, ch + 1, h);
  34.         }
  35.     }
  36. }
  37.  
  38. int mys(int len) {
  39.     return len - 1;
  40. }
  41.  
  42. signed main() {
  43.     ios_base::sync_with_stdio(false);
  44.     cin.tie(0);
  45.    
  46.     int n;
  47.     int a, b;
  48.     cin >> n >> a >> b;
  49.     a--;
  50.     b--;
  51.     used.resize(n);
  52.     g.resize(n);
  53.     for (int i = 0; i + 1 < n; i++) {
  54.         int u, v;
  55.         cin >> u >> v;
  56.         u--;
  57.         v--;
  58.         g[u].push_back(v);
  59.         g[v].push_back(u);
  60.     }
  61.     vector<int> ha(n);
  62.     vector<int> hb(n);
  63.     dfs(a, 0, ha);
  64.     fill(used.begin(), used.end(), 0);
  65.     dfs(b, 0, hb);
  66.     int ans = 0;
  67.     for (int i = 0; i < n; i++) {
  68.         if (hb[i] > ha[i]) {
  69.             ans = max(ans, ha[i] + mys(hb[i] - ha[i]));
  70.         }
  71.     }
  72.     cout << ans << endl;
  73. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement