Submission #1593154

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <climits>
using namespace std;

class LCA{
public:
    vector<int> dep;
    vector<vector<int>> par;
    LCA(int N, vector<vector<int>> &G, int s) : dep(N), par(N){
        vector<bool> isVisited(N, false);
        isVisited[s] = true;
        dfs1(N, G, isVisited, s, 0);
    
        int maxdepth = *max_element(dep.begin(), dep.end());
        int M = 1;
        for(int fac=1;; fac*=2){
            if(fac >= maxdepth) break;
            M++;
        }
        for(int i=0; i<N; i++) par[i].resize(M);
        par[s][0] = s;
        fill(isVisited.begin(), isVisited.end(), false);
        isVisited[s] = true;
        dfs2(N, M, G, isVisited, s);
    }
    void dfs1(int N, vector<vector<int>> &G, vector<bool> &isVisited, int s, int d){
        dep[s] = d;
        for(int t : G[s]){
            if(isVisited[t]) continue;
            isVisited[t] = true;
            dfs1(N, G, isVisited, t, d+1);
        }
    }
    void dfs2(int N, int M, vector<vector<int>> &G, vector<bool> &isVisited, int s){
        for(int i=1; i<M; i++)
            par[s][i] = par[par[s][i-1]][i-1];

        for(int t : G[s]){
            if(isVisited[t]) continue;
            isVisited[t] = true;
            par[t][0] = s;
            dfs2(N, M, G, isVisited, t);
        }
    }

    int get(int u, int v){
        int M = par[0].size();
        if(dep[u] > dep[v]) swap(u, v);
        int diff = dep[v] - dep[u];
        vector<int> vec;
        for(int i=0; i<M; i++)
            if(diff & (1 << i)) vec.push_back(i);
        reverse(vec.begin(), vec.end());
        for(int x : vec)
            v = par[v][x];

        if(u == v) return u;
        while(par[u][0] != par[v][0]){
            for(int i=M-1; i>=0; i--){
                if(par[u][i] != par[v][i]){
                    u = par[u][i];
                    v = par[v][i];
                }
            }
        }
        return par[u][0];
    }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<vector<int>> G(N);
    for(int i=0; i<N-1; i++){
        int x, y;
        cin >> x >> y;
        x--; y--;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    LCA lca(N, G, 0);
    int Q;
    cin >> Q;
    for(int i=0; i<Q; i++){
        int a, b;
        cin >> a >> b;
        a--; b--;
        int ab = lca.get(a, b);
        int ans = lca.dep[a]+lca.dep[b]-2*lca.dep[ab]+1;
        cout << ans << endl;
    }

    return 0;
}

Submission Info

Judge Result