Submission #1587312

---

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 int inf = 1e9;
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;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    const ll m = 30;
    ll n; cin >> n;
    vector<ll> h(n);
    vector<vector<ll>> par(m, vector<ll>(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);
    }
    function<void(ll,ll,ll)> dfs = [&](ll v, ll pv, ll d) {
        h[v] = d;
        par[0][v] = pv;
        each(to, G[v]) {
            if (to == pv) continue;
            dfs(to, v, d+1);
        }
    };
    dfs(0, 0, 0);
    rep(i, 1, m) rep(j, n) {
        par[i][j] = par[i-1][par[i-1][j]];
    }
    auto lca = [&](ll a, ll b) {
        // 高さをあわせる
        if (h[a] > h[b]) swap(a, b);
        // cout << a << " " << b << endl;
        rrep(i, m) {
            if (h[b]-h[a] >= (1LL<<i)) {
                b = par[i][b];
            }
        }
        assert(h[a] == h[b]);
        // にぶたん
        rrep(i, m) {
            if (par[i][a] != par[i][b]) {
                a = par[i][a];
                b = par[i][b];
            }
        }
        assert(a != b);
        assert(par[0][a] == par[0][b]);
        return par[0][a];
    };
    ll Q; cin >> Q;
    rep(q, Q) {
        ll a, b; cin >> a >> b; --a, --b;
        cout << h[a] + h[b] - 2 * h[lca(a, b)] + 1 << endl;
    }
}

Submission Info

Judge Result