結果

問題 No.2337 Equidistant
ユーザー sotanishy
提出日時 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.

ソースコード

diff # 

#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 depth
        for (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";
    }
}
0