• API
• FAQ
• Tools
• Archive
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.
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.         {
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;
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.
Top