結果

問題 No.2337 Equidistant
ユーザー otogawa
提出日時 2025-04-22 02:14:15
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,079 ms / 4,000 ms
コード長 2,579 bytes
コンパイル時間 2,682 ms
コンパイル使用メモリ 204,056 KB
実行使用メモリ 43,148 KB
最終ジャッジ日時 2025-04-22 02:14:37
合計ジャッジ時間 20,395 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    vector<vector<int>> g(n);
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v; --u, --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<int> sz(n), par(n), tin(n), tout(n), dep(n);
    int _t;
    auto dfs = [&] (auto&& self, int u, int p) -> void {
        dep[u] = dep[p] + 1;
        par[u] = p;
        sz[u] = 1;
        tin[u] = _t++;
        for (int v : g[u]) if (v != p) {
            self(self, v, u);
            sz[u] += sz[v];
        }
        tout[u] = _t;
    };
    dfs(dfs, 0, 0);
    int lg = __lg(n) + 1;
    vector table(lg, par);
    for (int p = 1; p < lg; p++) {
        for (int i = 0; i < n; i++) {
            table[p][i] = table[p - 1][table[p - 1][i]];
        }
    }
    auto f_k = [&] (int u, int k) {
        for (int p = 0; p < lg; p++) {
            if (k >> p & 1) {
                u = table[p][u];
            }
        }
        return u;
    };
    auto lca = [&] (int u, int v) {
        if (dep[u] > dep[v]) swap(u, v);
        int d = dep[v] - dep[u];
        for (int p = 0; p < lg; p++) {
            if (d >> p & 1) {
                v = table[p][v];
            }
        }
        if (u == v) return u;
        for (int p = lg - 1; p >= 0; p--) {
            if (table[p][u] != table[p][v]) {
                u = table[p][u];
                v = table[p][v];
            }
        }
        return par[u];
    };

    while (q--) {
        int u, v; cin >> u >> v; --u, --v;
        if (dep[u] > dep[v]) swap(u, v);

        if (tin[u] <= tin[v] && tout[v] <= tout[u]) { // u is ancestor of v
            int dist = dep[v] - dep[u];
            if (dist % 2) {
                cout << 0 << endl;
                continue;
            }

            int mid = f_k(v, dist / 2);
            int mid2 = f_k(v, dist / 2 - 1);
            cout << sz[mid] - sz[mid2] << endl;

            continue;
        }

        int l = lca(u, v);

        int du = dep[u] - dep[l];
        int dv = dep[v] - dep[l];
        int dist = du + dv;

        if (dist % 2) {
            cout << 0 << endl;
            continue;
        }

        if (du == dv) {
            int lu = f_k(u, du - 1);
            int lv = f_k(v, dv - 1);
            cout << sz[l] - sz[lu] - sz[lv] + (n - sz[l]) << endl;
        } else {
            int ref = (du > dv ? u : v);
            int mid = f_k(ref, dist / 2);
            int mid2 = f_k(ref, dist / 2 - 1);
            cout << sz[mid] - sz[mid2] << endl;
        }
    }

}
0