Advertisement
TwITe

Untitled

Nov 3rd, 2017
142
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.28 KB | None | 0 0
  1.  
  2. //
  3. //long long gcd(long long a, long long b) {
  4. //  if (a == 0) {
  5. //      return b;
  6. //  }
  7. //  return gcd(b % a, a);
  8. //}
  9. //
  10. //long long lcm(long long a, long long b) {
  11. //  return a * b / gcd(a, b);
  12. //}
  13.  
  14. vector <vector <int>> v;
  15. vector <int> maxh;
  16. vector <bool> used;
  17.  
  18. void dfs1(int node, vector <int> &dist, int length) {
  19.     dist[node] = length;
  20.     used[node] = 1;
  21.     for (int i = 0; i < v[node].size(); i++)
  22.     {
  23.         if (!used[i]) {
  24.             dfs1(v[node][i], dist, length + 1);
  25.         }
  26.     }
  27. }
  28.  
  29. void dfs2(int node, int length)
  30. {
  31.     used[node] = 1;
  32.     maxh[node] = length;
  33.     for (int i = 0; i < v[node].size(); i++) {
  34.         if (!used[i]) {
  35.             dfs2(i, length + 1);
  36.             maxh[node] = max(maxh[node], maxh[i]);
  37.         }
  38.     }
  39. }
  40.  
  41. void task1() {
  42.     int n, x;
  43.     cin >> n >> x;
  44.     --x;
  45.     v.resize(n);
  46.     used.resize(n + 1);
  47.     for (int i = 1; i < n; i++) {
  48.         int a, b;
  49.         cin >> a >> b;
  50.         --a, --b;
  51.         v[a].push_back(b);
  52.         v[b].push_back(a);
  53.     }
  54.     vector <vector <int>> d(2, vector <int> (n));
  55.     used.assign(n, false);
  56.     dfs1(0, d[0], 0);
  57.     used.assign(n, false);
  58.     dfs1(x, d[1], 0);
  59.     used.assign(n, false);
  60.     maxh.resize(n);
  61.     dfs2(0, 0);
  62.     int res = 0;
  63.     for (int i = 0; i < n; i++) {
  64.         if (d[1][i] < d[0][i]) {
  65.             res = max(res, maxh[i]);
  66.         }
  67.     }
  68.     cout << 2 * res;
  69. }
  70.  
  71. int main() {
  72.     task1();
  73.     system("PAUSE");
  74. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement