This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub SSRS-cp/cp_library
#define PROBLEM "https://yukicoder.me/problems/no/1326" #include <bits/stdc++.h> using namespace std; #include "../../graph/extended_block_cut_tree.hpp" #include "../../data_structure/tree/heavy_light_decomposition.hpp" int main(){ int N, M; cin >> N >> M; vector<vector<int>> E(N); for (int i = 0; i < M; i++){ int a, b; cin >> a >> b; a--; b--; E[a].push_back(b); E[b].push_back(a); } extended_block_cut_tree T(E); int V = T.size(); vector<int> p(V, -1); vector<vector<int>> c(V); vector<int> d(V, 0); queue<int> q; q.push(0); while (!q.empty()){ int v = q.front(); q.pop(); for (int w : T[v]){ if (w != p[v]){ p[w] = v; c[v].push_back(w); d[w] = d[v] + 1; q.push(w); } } } heavy_light_decomposition HLD(p, c); int Q; cin >> Q; for (int i = 0; i < Q; i++){ int x, y; cin >> x >> y; x--; y--; cout << max(HLD.dist(x, y) / 2 - 1, 0) << endl; } }
#line 1 "test/yukicoder/yuki_1326_2.test.cpp" #define PROBLEM "https://yukicoder.me/problems/no/1326" #include <bits/stdc++.h> using namespace std; #line 2 "graph/extended_block_cut_tree.hpp" /** * @brief 拡張 Block Cut Tree */ struct extended_block_cut_tree{ int N, cnt; vector<vector<int>> G; extended_block_cut_tree(vector<vector<int>> &E){ N = E.size(); vector<int> next(N, -1); vector<int> d(N, -1); vector<int> imos(N, 0); for (int i = 0; i < N; i++){ if (d[i] == -1){ d[i] = 0; dfs1(E, next, d, imos, i); } } cnt = 0; G.resize(N + 1); vector<bool> used(N, false); for (int i = 0; i < N; i++){ if (d[i] == 0){ dfs2(E, d, imos, used, cnt, i); } if (E[i].empty()){ G[i].push_back(N + cnt); G[N + cnt].push_back(i); cnt++; G.push_back({}); } } G.pop_back(); } void dfs1(vector<vector<int>> &E, vector<int> &next, vector<int> &d, vector<int> &imos, int v){ for (int w : E[v]){ if (d[w] == -1){ d[w] = d[v] + 1; next[v] = w; dfs1(E, next, d, imos, w); imos[v] += imos[w]; } else if (d[w] < d[v] - 1){ imos[v]++; imos[next[w]]--; } } } void dfs2(vector<vector<int>> &E, vector<int> &d, vector<int> &imos, vector<bool> &used, int b, int v){ used[v] = true; bool ok = false; for (int w : E[v]){ if (d[w] == d[v] + 1 && !used[w]){ if (imos[w] > 0){ if (!ok){ ok = true; G[v].push_back(N + b); G[N + b].push_back(v); } dfs2(E, d, imos, used, b, w); } else { G[v].push_back(N + cnt); G[N + cnt].push_back(v); cnt++; G.push_back({}); dfs2(E, d, imos, used, cnt - 1, w); } } } if (!ok && d[v] > 0){ G[v].push_back(N + b); G[N + b].push_back(v); } } int size(){ return G.size(); } vector<int> &operator [](int v){ return G[v]; } }; #line 2 "data_structure/tree/heavy_light_decomposition.hpp" /** * @brief 重軽分解 */ struct heavy_light_decomposition{ vector<int> p, sz, in, next; void dfs1(vector<vector<int>> &c, int v){ sz[v] = 1; for (int &w : c[v]){ dfs1(c, w); sz[v] += sz[w]; if (sz[w] > sz[c[v][0]]){ swap(w, c[v][0]); } } } void dfs2(vector<vector<int>> &c, int &t, int v){ in[v] = t; t++; for (int w : c[v]){ if (w == c[v][0]){ next[w] = next[v]; } else { next[w] = w; } dfs2(c, t, w); } } heavy_light_decomposition(vector<int> &p, vector<vector<int>> &c, int r = 0): p(p){ int N = p.size(); sz = vector<int>(N); dfs1(c, r); in = vector<int>(N); next = vector<int>(N, r); int t = 0; dfs2(c, t, r); } int lca(int u, int v){ while (true){ if (in[u] > in[v]){ swap(u, v); } if (next[u] == next[v]){ return u; } v = p[next[v]]; } } int dist(int u, int v){ int ans = 0; while (true){ if (in[u] > in[v]){ swap(u, v); } if (next[u] == next[v]){ ans += in[v] - in[u]; return ans; } ans += in[v] - in[next[v]] + 1; v = p[next[v]]; } } }; #line 6 "test/yukicoder/yuki_1326_2.test.cpp" int main(){ int N, M; cin >> N >> M; vector<vector<int>> E(N); for (int i = 0; i < M; i++){ int a, b; cin >> a >> b; a--; b--; E[a].push_back(b); E[b].push_back(a); } extended_block_cut_tree T(E); int V = T.size(); vector<int> p(V, -1); vector<vector<int>> c(V); vector<int> d(V, 0); queue<int> q; q.push(0); while (!q.empty()){ int v = q.front(); q.pop(); for (int w : T[v]){ if (w != p[v]){ p[w] = v; c[v].push_back(w); d[w] = d[v] + 1; q.push(w); } } } heavy_light_decomposition HLD(p, c); int Q; cin >> Q; for (int i = 0; i < Q; i++){ int x, y; cin >> x >> y; x--; y--; cout << max(HLD.dist(x, y) / 2 - 1, 0) << endl; } }