結果

問題 No.2337 Equidistant
ユーザー sotanishysotanishy
提出日時 2023-06-02 22:00:23
言語 C++17(clang)
(17.0.6 + boost 1.83.0)
結果
AC  
実行時間 1,196 ms / 4,000 ms
コード長 3,574 bytes
コンパイル時間 3,987 ms
コンパイル使用メモリ 132,940 KB
実行使用メモリ 42,984 KB
最終ジャッジ日時 2023-08-28 03:28:33
合計ジャッジ時間 18,311 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 4 ms
4,380 KB
testcase_07 AC 3 ms
4,376 KB
testcase_08 AC 3 ms
4,376 KB
testcase_09 AC 3 ms
4,376 KB
testcase_10 AC 3 ms
4,376 KB
testcase_11 AC 642 ms
30,524 KB
testcase_12 AC 596 ms
30,576 KB
testcase_13 AC 603 ms
30,580 KB
testcase_14 AC 581 ms
30,528 KB
testcase_15 AC 588 ms
30,548 KB
testcase_16 AC 604 ms
30,576 KB
testcase_17 AC 597 ms
30,516 KB
testcase_18 AC 638 ms
30,548 KB
testcase_19 AC 600 ms
30,528 KB
testcase_20 AC 624 ms
30,512 KB
testcase_21 AC 587 ms
42,984 KB
testcase_22 AC 587 ms
31,124 KB
testcase_23 AC 545 ms
31,208 KB
testcase_24 AC 839 ms
38,752 KB
testcase_25 AC 612 ms
31,216 KB
testcase_26 AC 1,196 ms
38,756 KB
testcase_27 AC 679 ms
31,212 KB
testcase_28 AC 674 ms
31,232 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:18:5: warning: explicitly defaulted default constructor is implicitly deleted [-Wdefaulted-function-deleted]
    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
    const std::vector<std::vector<int>>& G;
                                         ^
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