Submission #7483038

---

Source Code Expand

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

vector<vector<int> > tree(100010);

template< typename G >
struct DoublingLowestCommonAncestor {
    const int LOG;
    vector< int > dep;
    const G &g;
    vector< vector< int > > table;

    DoublingLowestCommonAncestor(const G &g) : g(g), dep(g.size()), LOG(32 - __builtin_clz(g.size())) {
        table.assign(LOG, vector< int >(g.size(), -1));
    }

    void dfs(int idx, int par, int d) {
        table[0][idx] = par;
        dep[idx] = d;
        for(auto &to : g[idx]) {
            if(to != par) dfs(to, idx, d + 1);
        }
    }

    void build() {
        dfs(0, -1, 0);
        for(int k = 0; k + 1 < LOG; k++) {
            for(int i = 0; i < table[k].size(); i++) {
                if(table[k][i] == -1) table[k + 1][i] = -1;
                else table[k + 1][i] = table[k][table[k][i]];
            }
        }
    }

    int query(int u, int v) {
        if(dep[u] > dep[v]) swap(u, v);
        for(int i = LOG - 1; i >= 0; i--) {
            if(((dep[v] - dep[u]) >> i) & 1) v = table[i][v];
        }
        if(u == v) return u;
        for(int i = LOG - 1; i >= 0; i--) {
            if(table[i][u] != table[i][v]) {
                u = table[i][u];
                v = table[i][v];
            }
        }
        return table[0][u];
    }
};

int dist[100010] = {};
int used[100010];

void dfs(int i, int d){
    dist[i] = d;
    used[i] = 1;

    for(int j = 0;j < tree[i].size();j++){
        if(!used[tree[i][j]]){
            dfs(tree[i][j], d+1);
        }
    }
    return;
}

int main(){
    int n;
    int x, y;
    cin >> n;

    for(int i = 0;i < n-1;i++){
        cin >> x >> y;
        x--; y--;
        tree[x].push_back(y);
        tree[y].push_back(x);
    }

    DoublingLowestCommonAncestor<vector<vector<int> > >  lca(tree);
    lca.build();
    dfs(0, 0);


    int q; cin >> q;
    for(int p = 0;p < q;p++){
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        cout << dist[a] + dist[b] - 2 * dist[lca.query(a, b)] +1 << endl;
    }

    return 0;
}

Submission Info

Judge Result