SHARE
TWEET

Untitled

a guest Feb 14th, 2020 73 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define all(x) begin(x), end(x)
  3. #define dbg(x) cerr << #x << " = " << x << endl
  4. #define _ << ' ' <<
  5. using namespace std;
  6. using ll = long long;
  7. using vi = vector<int>;
  8.  
  9. vi adj[200005], adj2[200005];
  10. int jump[200005][18];
  11. int in[200005], jin[200005], out[200005];
  12. int low[200005];
  13. int sum[200005];
  14. int val[200005];
  15. int tick = 1;
  16.  
  17. void dfs(int x, int p)
  18. {
  19.     in[x] = low[x] = tick++;
  20.     for (int y : adj[x])
  21.     {
  22.         if (y == p)
  23.             continue;
  24.  
  25.         if (in[y] == 0)
  26.         {
  27.             adj2[x].push_back(y);
  28.             adj2[y].push_back(x);
  29.             dfs(y, x);
  30.             low[x] = min(low[x], low[y]);
  31.         }
  32.         else
  33.             low[x] = min(low[x], in[y]);
  34.     }
  35. }
  36.  
  37. void dfs2(int x, int p)
  38. {
  39.     for (int y : adj2[x])
  40.     {
  41.         if (y == p)
  42.             continue;
  43.  
  44.         if (low[y] >= in[x])
  45.             val[y] = 1;
  46.  
  47.         sum[y] = sum[x] + val[y];
  48.         dfs2(y, x);
  49.     }
  50. }
  51.  
  52.  
  53. void dfs3(int x, int p)
  54. {
  55.     jump[x][0] = (p == -1 ? x : p);
  56.     for (int i = 1; i < 18; ++i)
  57.         jump[x][i] = jump[jump[x][i - 1]][i - 1];
  58.  
  59.     jin[x] = tick++;
  60.     for (int y : adj2[x])
  61.         if (y != p)
  62.             dfs3(y, x);
  63.     out[x] = tick++;
  64. }
  65.  
  66. bool is_ancestor(int x, int y)
  67. {
  68.     return jin[x] <= jin[y] && out[y] <= out[x];
  69. }
  70.  
  71. int lca(int x, int y)
  72. {
  73.     if (is_ancestor(x, y)) return x;
  74.     for (int i = 18 - 1; i >= 0; --i)
  75.         if (!is_ancestor(jump[x][i], y))
  76.             x = jump[x][i];
  77.     return jump[x][0];
  78. }
  79.  
  80. int llca(int x, int y)
  81. {
  82.     for (int i = 18 - 1; i >= 0; --i)
  83.         if (!is_ancestor(jump[x][i], y))
  84.             x = jump[x][i];
  85.     return x;
  86. }
  87.  
  88. int main()
  89. {
  90.     ios::sync_with_stdio(false);
  91.     cin.tie(0);
  92.     int n, m;
  93.     cin >> n >> m;
  94.     for (int i = 0; i < m; ++i)
  95.     {
  96.         int u, v;
  97.         cin >> u >> v;
  98.         adj[u].push_back(v);
  99.         adj[v].push_back(u);
  100.     }
  101.    
  102.     dfs(1, -1);
  103.     dfs2(1, -1);
  104.     dfs3(1, -1);
  105.  
  106.     int q;
  107.     cin >> q;
  108.     while (q--)
  109.     {
  110.         int c, d;
  111.         cin >> c >> d;
  112.         int l = lca(c, d);
  113.         int s = sum[c] + sum[d];
  114.         if (l != c && l != d)
  115.         {
  116.             s -= 2 * sum[l];
  117.             int a = llca(c, d);
  118.             int b = llca(d, c);
  119.             s -= val[a] + val[b];
  120.             s++;
  121.             if (low[a] < in[l] && low[b] < in[l])
  122.                 s--;
  123.         }
  124.         else
  125.         {
  126.             if (!is_ancestor(c, d)) swap(c, d);
  127.             int b = llca(d, c);
  128.             s -= sum[l];
  129.             s -= sum[b];
  130.         }
  131.         cout << s << '\n';
  132.     }
  133. }
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