Guest User

Untitled

a guest
Jul 20th, 2017
751
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.26 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define e1 first
  4. #define e2 second
  5. #define pb push_back
  6. #define mp make_pair
  7. #define boost ios_base::sync_with_stdio(false)
  8. #define eb emplace_back
  9. #define OUT(x) {cout << x; exit(0); }
  10. #define FOR(i,a,b) for(int i=(a);i<=(b);++i)
  11. #define scanf(...) scanf(__VA_ARGS__)?:0
  12. typedef long long int ll;
  13. typedef unsigned long long ull;
  14. typedef pair <int, int> PII;
  15. typedef pair <ll, ll> PLL;
  16. typedef pair <PLL, int> PLLI;
  17. typedef pair <PLL, PLL> PP;
  18. typedef pair <PII, int> PPI;
  19. typedef pair <ll, int> PLI;
  20. typedef unsigned int ui;
  21. const int inf = 1e9+9;
  22. const ll MOD = 1e9+696969;
  23. const long long INF = 1e18+3;
  24. #define maxn 1001000
  25. vector <int> v[maxn];
  26. int parent[maxn], n, root, goal, a ,b, d[maxn];
  27. bool onpath[maxn];
  28. int POST[maxn], VER;
  29. void countEverything(int x, int par)
  30. {
  31.     parent[x] = par;
  32.     for (auto u : v[x])
  33.         if (u != par)
  34.         {
  35.             d[u] = d[x] + 1;
  36.             countEverything(u, x);
  37.         }
  38.     POST[++VER] = x;
  39. }
  40.  
  41. int cost[maxn];
  42. inline int deg(int x) {
  43.     return (int)v[x].size();
  44. }
  45. int sciezka[maxn], DS;
  46.  
  47. void dfs(int x, int par) {
  48.     //cout << "Where am i: " << x << endl;
  49.     for (auto u : v[x])
  50.         if (!onpath[u] && u != par)
  51.         {
  52.             cost[u] = cost[x] + deg(u) - 1;
  53.             dfs(u, x);
  54.         }
  55. }
  56. bool zle[maxn];
  57. int dp[maxn];
  58. bool check(int k)
  59. {
  60.     FOR(i, 1, n) dp[i] = 0;
  61.     FOR(i, 1, n)
  62.     {
  63.         int x = POST[i];
  64.         dp[x]--;
  65.         if (cost[x] > k) dp[x] = 1;
  66.         else dp[x] = max(0, dp[x]);
  67.         dp[x] = min(dp[x], 1);
  68.         if (x != root) dp[parent[x]] += dp[x];
  69.     }
  70.     return (dp[root] == 0);
  71. }
  72.  
  73. int main()
  74. {
  75.     ios_base::sync_with_stdio(0);
  76.     cin.tie(0); cout.tie(0);
  77.     cin >> n >> goal >> root;
  78.     assert(goal <= n); assert(root <= n);
  79.     if (goal == root) OUT(0);
  80.     FOR(i, 2, n)
  81.     {
  82.         cin >> a >> b;
  83.         v[a].pb(b);
  84.         v[b].pb(a);
  85.     }
  86.     countEverything(root, root);
  87.     int x = goal, y = 0;
  88.     while (x != root)
  89.     {
  90.         onpath[x] = 1;
  91.         sciezka[++DS] = x;
  92.         x = parent[x];
  93.     }
  94.     onpath[root] = 1;
  95.     sciezka[++DS] = x;
  96.     int pathOnly = 0;
  97.    
  98.     pathOnly -= (d[goal] - 1);
  99.     FOR(i, 1, DS)
  100.     {
  101.         int u = sciezka[i];
  102.         if (u != goal) pathOnly += deg(sciezka[i]) - 1;
  103.         if (u != goal) dfs(u, u);
  104.     }
  105.  
  106.     x = 0, y = n + n;
  107.     while (x < y)
  108.     {
  109.         int sr = (x + y) >> 1;
  110.         if (!check(sr)) x = ++sr;
  111.         else y = sr;
  112.     }
  113.  
  114.     cout << pathOnly + x;
  115. }
Advertisement
Add Comment
Please, Sign In to add comment