Submission #1756045

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

#define each(i,a) for (auto&& i : a)
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define chmin(x,v) x = min(x, v)
#define chmax(x,v) x = max(x, v)

const ll linf = 1e18;
const double eps = 1e-12;
const double pi = acos(-1);

template<typename T>
istream& operator>>(istream& is, vector<T>& vec) {
    each(x,vec) is >> x;
    return is;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
    rep(i,vec.size()) {
        if (i) os << " ";
        os << vec[i];
    }
    return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector< vector<T> >& vec) {
    rep(i,vec.size()) {
        if (i) os << endl;
        os << vec[i];
    }
    return os;
}

const ll lg = 30;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n; cin >> n;
    vector<vector<ll>> G(n);
    rep(i, n-1) {
        ll a, b; cin >> a >> b; --a, --b;
        G[a].pb(b);
        G[b].pb(a);
    }
    vector<vector<ll>> par(n, vector<ll>(lg));
    vector<ll> h(n);
    function<void(ll, ll, ll)> dfs = [&](ll v, ll prev, ll depth) {
        par[v][0] = prev;
        h[v] = depth;
        each(to, G[v]) {
            if (to == prev) continue;
            dfs(to, v, depth+1);
        }
    };
    dfs(0, -1, 0);
    rep(i, 1, lg) rep(j, n) {
        ll p = par[j][i-1];
        if (p < 0) par[j][i] = -1;
        else par[j][i] = par[p][i-1];
    }
    auto lca = [&](ll a, ll b) {
        if (h[a] > h[b]) swap(a, b);
        ll d = h[b]-h[a];
        rep(i, lg) {
            if (d & (1LL<<i)) {
                b = par[b][i];
            }
        }
        assert(b >= 0 && h[a] == h[b]);
        if (a == b) return a;
        rrep(i, lg) {
            if (par[a][i] != par[b][i]) {
                a = par[a][i];
                b = par[b][i];
            }
            assert(a != b);
        }
        return par[a][0];
    };
    ll Q; cin >> Q;
    rep(q, Q) {
        ll a, b; cin >> a >> b; --a, --b;
        // cout << "!" << a << " " << b << " " << lca(a, b) << endl;
        // cout << h[a] << " " << h[b] << " " << endl;
        cout << h[a] + h[b] - h[lca(a, b)]*2 + 1 << endl;
    }
}

Submission Info

Judge Result