結果
問題 | No.2337 Equidistant |
ユーザー |
![]() |
提出日時 | 2023-06-02 22:00:23 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 842 ms / 4,000 ms |
コード長 | 3,574 bytes |
コンパイル時間 | 8,279 ms |
コンパイル使用メモリ | 164,636 KB |
実行使用メモリ | 42,956 KB |
最終ジャッジ日時 | 2024-12-28 17:53:55 |
合計ジャッジ時間 | 23,012 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
コンパイルメッセージ
main.cpp:18:5: warning: explicitly defaulted default constructor is implicitly deleted [-Wdefaulted-function-deleted] 18 | LCA() = default; | ^ main.cpp:79:42: note: default constructor of 'LCA' is implicitly deleted because field 'G' of reference type 'const std::vector<std::vector<int>> &' would not be initialized 79 | const std::vector<std::vector<int>>& G; | ^ main.cpp:18:13: note: replace 'default' with 'delete' 18 | LCA() = default; | ^~~~~~~ | delete 1 warning generated.
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;#define rep(i, s, t) for (int i = (int)(s); i < (int)(t); ++i)#define revrep(i, t, s) for (int i = (int)(t)-1; i >= (int)(s); --i)#define all(x) begin(x), end(x)template <typename T>bool chmax(T& a, const T& b) {return a < b ? (a = b, 1) : 0;}template <typename T>bool chmin(T& a, const T& b) {return a > b ? (a = b, 1) : 0;}class LCA {public:LCA() = default;LCA(const std::vector<std::vector<int>>& G, int root): G(G), LOG(32 - __builtin_clz(G.size())), depth(G.size()) {int V = G.size();table.assign(LOG, std::vector<int>(V, -1));dfs(root, -1, 0);for (int k = 0; k < LOG - 1; ++k) {for (int v = 0; v < V; ++v) {if (table[k][v] >= 0) {table[k + 1][v] = table[k][table[k][v]];}}}}int query(int u, int v) const {if (depth[u] > depth[v]) std::swap(u, v);// go up to the same depthfor (int k = 0; k < LOG; ++k) {if ((depth[v] - depth[u]) >> k & 1) {v = table[k][v];}}if (u == v) return u;for (int k = LOG - 1; k >= 0; --k) {if (table[k][u] != table[k][v]) {u = table[k][u];v = table[k][v];}}return table[0][u];}int dist(int u, int v) const {return depth[u] + depth[v] - 2 * depth[query(u, v)];}int parent(int v, int k) const {for (int i = LOG - 1; i >= 0; --i) {if (k >= (1 << i)) {v = table[i][v];k -= 1 << i;}}return v;}int jump(int u, int v, int k) const {int l = query(u, v);int du = depth[u] - depth[l];int dv = depth[v] - depth[l];if (du + dv < k) return -1;if (k < du) return parent(u, k);return parent(v, du + dv - k);}protected:const std::vector<std::vector<int>>& G;const int LOG;std::vector<std::vector<int>> table;std::vector<int> depth;void dfs(int v, int p, int d) {table[0][v] = p;depth[v] = d;for (int c : G[v]) {if (c != p) dfs(c, v, d + 1);}}};int main() {ios_base::sync_with_stdio(false);cin.tie(nullptr);cout << fixed << setprecision(15);int N, Q;cin >> N >> Q;vector<vector<int>> G(N);rep(i, 0, N - 1) {int a, b;cin >> a >> b;--a, --b;G[a].push_back(b);G[b].push_back(a);}LCA lca(G, 0);vector<int> sz(N, 1), par(N, -1);auto dfs = [&](auto& dfs, int v) -> void {for (int c : G[v]) {if (c != par[v]) {par[c] = v;dfs(dfs, c);sz[v] += sz[c];}}};dfs(dfs, 0);while (Q--) {int s, t;cin >> s >> t;--s, --t;int d = lca.dist(s, t);if (d % 2 == 1) {cout << 0 << "\n";continue;}int m = lca.jump(s, t, d / 2);int ans = N;int vs = lca.jump(m, s, 1);if (vs == par[m]) {ans -= N - sz[m];} else {ans -= sz[vs];}int vt = lca.jump(m, t, 1);if (vt == par[m]) {ans -= N - sz[m];} else {ans -= sz[vt];}cout << ans << "\n";}}